I'm trying out purelymail (basically one dude's AWS hosting of email for $10/yr) and I'm having the same problem with my custom domain: google stopped having issues after the first few emails I sent got marked as "not spam", but microsoft, despite the purelymail guy filling out all the requisite forms, still eats all of my email, not even sending it to the spam folder of the addresses I'm sending to.