I'm having a similar problem with one of my hosts.

Apparently the IP address that I now have is listed in the sorbs.net block list.

Many email hosts use these blacklists to filter spam.

They have instructions for how to get your IP address removed, but it all seems like a pain in the ....

Another site I have on a more reputable hosting company has never had such a problem.

I'm thinking of moving over for the few bucks extra a month. I know it's not a guarantee, but I also get better support and a better webmail interface.

The e-mail issue is just the final straw...