I've been using mailu.io to host my own email server. Makes it real easy to manage yourself.

I haven't had any issues with new domains being marked as spam, but I always make sure the SPF, DKIM and DMARC records are set up.