The solution *could* be to host their own mail server if it were made
easy enough for them. I'm thinking something like a Raspberry Pi with
very well designed web UI for simple configuration and management.
Include a nice webmail client and even most non-techies could probably
do this.