Stupid anti spam services, that is the future of the Internet, everyone delegating their email filter (and comment filtering as well) to third parties. Well guess what is happing people, the filtering systems are lazy and now it's simple: If your domain does not generate enough traffic or is not "important" enough then your emails just get junked. Done. You can be as careful as you want, as strict as you can possibly be it does not matter. After 8 years of operating my mail server, not 1 spam has been sent and yet my emails get tagged and junked half the time while at the same time I receive so much spam from actual verified hotmail accounts (that have been hacked of course) as well as from other domains.
What can you do ? For starters you can contact your email provider, tell them you would like to know how their filters work, on what basis does a domain become a suspected spam source ? Ask if you can change the level of filtering and such (I offer this to my users, they chose if they filter and to what extent). Oh but wait, because it's all free (and you are too cheap to consider email services worth any of your money) I don't think you have ANY say in that. So maybe you could get a real email service, you know the thing that you pay for and that owes you some kind of service and such things. I only say this because I have sent many emails to hotmail and apart from the auto-replies I have received nothing. The situation has changed, back in the olden days I'd get the AOL people on the phone and we'd solve things (like adding my static home IP to their whitelist), (never thought I'd say anything good about AOL).
So there are now 2 solutions for me, 1. give up and get a gyahoomail account, or 2. or start rejecting emails from servers/domains who don't have any respect for proper SMTPing. This is the price of a privatised Internet.