Originally Posted by Publisher Bucks

Dedicated hosting or shared?

It is entirely possible if shared that someone else using the same IP has been blocked and its effected your sites, happened to me about 6 years ago, some Bulgarian SEO spammer had a bunch of domains and it ended up killing a few people on the same servers rankings.