I may have some information about this, but it's a little bit crude. It comes from Adam Curry's Daily Source Code podcast, when he was first setting up his startup Podshow and was having similar troubles (and not just with Hotmail -- all the webmail providers!).

Btw, the first thing I would do is get SenderID working. It will work with almost everything -- sendmail and postfix at least, so I'd bet that it works with qmail too.

According to what Adam says he found, you have to be registered with some sort of clearing house or all the webmail providers will drop you as spam. This is not senderid or spf. The only efficient way to be 'registered' is to purchase and appliance from a company for upwards of $80K. I think this includes configuring it with your domain info as well.

I wish my 'info' was not so vague. It comes from 1+ years ago, and Adam was never super-clear about specifics. It always sounded a little weird to me, but OTOH I do believe the webmail providers would do this. Apparently, it's done in the name of anti-spam, but the spammers are allowed to buy these appliances, so it's really about milking more money from emailers, and maybe about squeezing out the little guy.

I'm hoping someone out there can clear some of this up, because it's a problem we all potentially face (if it's real).