It's easiest to just get a new clean IP. Oddly I just discovered that this site thinks one of my servers hosts a Fortune 500 (Actually within the top 50) company's main website.
What happened is likely that the IP was previously allocated to them in the past or there may be some bad dns entries somewhere.