You should be fine on the big providers. There's a weird horseshoe situation where anti-Google doomposting looks a lot like pro-Google FUD that I think leads people to believe only Google and maybe Microsoft are capable of sending mail any more.
Something like mailbox.org should be fine. Even a carefully-chosen VPS running your own email server should be fine (works for me, no delivery problems in ~2 years)