I feel your pain, man. Sadly, it's impossible to reliably deliver email to Microsoft if you aren't a big player.
You can have a clean domain, clean IP, comply with all the standards... whatever, they don't care. I'm sorry but I hate them for this (and other things). I've lost countless hours...