I can second Hetzner. In my case with their dedicated offering, though. Been running mail servers there since at least 2013 with next to no problems.

Google sometimes put mails into the spam folder, though not in recent times. Microsoft tends to block unused IP addresses by default, there's a Wiki page on how to request an unblock: https://wiki.hetzner.de/index.php/Microsoft_Blacklist/en

I sign all my emails using DKIM and have good domain reputation.