This is a good read about SMTP and why it’s a bad idea to roll with the big 5:

We’re currently at a point where it is even difficult to run your own mailserver because small mailservers tend to end up on some blocklist thanks to “bad neighbourhood”. That’d be ips “next” to you. Getting removed again – even for no reason – is a PITA, because there is no unified way of doing so. Happened again and again and while the big 5 won’t bother blocking entire ranges most of the spam bouncing of my own mailserver is indeed from the big mailserves themself. So nowadays I simply stopped caring at all.

My advice for affected people is the same: Use a smaller provider or even run your own. Do not use the mailservices of the big companies. It’s not that hard. Even a consumer NAS can do it.