This place will let you know if it's you (or your ISP) that's being blacklisted for spamming:
http://www.spamhaus.org/lookup.lasso. Just type in your IP (
http://whatsmyip.org/ if you're not sure what it is). There are a few blacklists that ISPs use, not sure what Microsoft uses, but I'm pretty sure it's a European company (Spamfighter? - I think they bought them, but maybe not). If you're being blacklisted and using DSL, contact your ISP. If you have a cable modem, try resetting it and drawing a new IP; otherwise call the cable company.
I love gmail and have a hotmail account too. Hotmail's OK, but constantly playing catchup with google. Google's spam filtering seems much more effective, too, with less false positives. They give you so much free space you can literally use them for backups, plus you don't have to log in once a month to keep your account active.
If you or anyone else wants a gmail address I still have over 90 invites. Not sure if you still need to be invited or not, but if so let me know and I'll send you one.
Resolve then, that on this very ground, with small flags waving and tinny blasts on tiny trumpets, we shall meet the enemy, and not only may he be ours, he may be us. --Walt Kelly