I'm self-hosting my mail server without a relay. It is still possible, you just need to be persistent. In the beginning Microsoft might just let your mails vanish and while they won't confirm this when you contact them doing so eventually resolved my delivery issues with their mail servers. With Google I didn't have any issues.