I don't know if it's my imagination, but emails of mine sent via my domain and not gmail or outlook seem to often mysteriously vanish, and I was thinking it may be because they are flagged as spam.

There's also the issue that nothing other than gmail works very well on an android phone.

I started using email long before Google existed, but I'm not really familiar with a good alternative at this point. It's not that I wouldn't theoretically pay money for a good old fashioned email provider with human customer service, but I really don't think such a business exists anymore, due to the proliferation of free email. And a small-time automated business is going to be worse than a big-time automated business anyway. It's just not 1993 any more.