It pains me to think I am on MS's side here, but...
I'm not sure why people expect that five minutes after they register a domain and fire up their VPS they are going to be delivering straight into every inbox in the world.
If you want to work on the problem, more info than you probably want is available at
http://postmaster.live.com/
AFAIK a big part of MS's first layer of anti-spam is based on the sender "reputation". So if you just put up a new server on a new domain, you have zero reputation and they assume (probably correctly, nothing personal) that you're a spammer. Running through their assorted hoops is supposed to be a way to jumpstart the process I think, but I've never done anything special and my domains seem perfectly able to deliver to hotmail.
And RFC-compliant or not, lots of servers blackhole messages they don't like. If you have any serious volume you can't do content filtering at SMTP time, so your spam/virus filters either blackhole or (worse) send NDR's.