Planet13 - 2:28 pm on Nov 12, 2011 (gmt 0)
A couple of things come to mind...
Is your business based in the UK or in in the US? Matt Cutts did say that server location COULD affect SERP position.
Also, how reputable is the hosting company and their servers? Matt Cutts has said that there are instances where a particular shared server with LOTS of bad domains on it COULD affect the ability of legitimate companies on the same server to rank well.
You also mentioned:
5. Many old URLs have been combined and .301 redirected to one of the new URLs above.
How RELEVANT are the new URLs to the old ones (which have been redirected by 301 headers)?
I have been told by the moderators in this forum that they have seen instances where playing fast and loose with too many 301 redirects has hurt a site's rankings.
One last thing: Can I ask why you didn't file DMCA requests with google to have the offending sites removed from the index? Was there just too many of them?