This issue appears to have been resolved. Kind of funny actually. I had been dealing with the Host Monster ticket system and it was taking 24 hours to get a reply. This morning I made a post to Matt Heaton’s blog (CEO of Blue Host) about the problem. It was resolved within hours and I’ve already received 3 follow ups from support.
Host Monster support states that the problem was D-Shield put themselves (and I assume Cisco as well) on their own ban list. I spoke with Johannes at D-Shield. I’ve known him for 10 years and he’s a real straight shooter. He had no clue what they are talking about and had not heard of this problem with anyone else. Sounds a little funny to me, because if they were actually using D-Shield to generate a ban list they would have known they were the good guys last Thursday when I first contacted support.
In any event it appears that all of the previously mentioned blocks have been cleared. Who says security and day time soap operas have nothing in common. 
Related posts:
Hey there Chris:
It has been a while since I took your SANS Perimeter Security class back in 2003. Hope all is well with you and your family.
Your situation above reminds me of the time I was doing firewall support from home and my ISP (SBC/AT&T) block all my access to and from CheckPoint because they were “a bad spamming site”. Took nearly a week to clear up and I had to commute to the office (100 miles in each direction) while I had the issues.
Regards,
CJ Ondeck
God hearing from you CJ,
Ouch! I feel your pain. I think many times it comes back to reliability of feedback. Users will receive e-mail from a company and be afraid that trying to unsubscribe will only make things worse. So the user takes the easy way out and just marks the e-mail as spam. If a couple of users do this, the ISP puts the source on a blacklist.
Makes you seriously think about risk and the benefits of a raw connection.