"in fact the search engines and Facebook have hardly complied -- there are still search results and Facebook pages for this company"
The DMCA doesn't require that links to the company be removed - it requires that the service provider stop their distribution of a copyrighted work. From TFA, it sounds like only Facebook had a direct download link to the copyrighted work, and that they assisted in its removal. As someone else mentioned, to make the download completely unavailable you would need to send a DMCA notice to the hosting provider (Masterhost, according to RIPE) and hope that this Russian company respects U.S. copyright law.
Getting search engines to delist entire companies isn't really what the law is intended for, even if it sometimes succeeds.