Yeah, that's my experience too. Google doesn't like new domains, but at least accepts mail and delivers to spam (or to the inbox once the domain is old enough). Microsoft just refuses all mail if you host on a VPS whenever someone else on the block (NOT the same IP) misbehaves (or is accused of misbehaving, not sure).