It certainly could be an issue, but honestly even if it were possible to set up my own mail server, that's even worse for pseudonymity than a google account because ICANN records are public and I'd be the only one using my domains. It would make it much easier for some random person to uniquely identify me, which is a worse threat than Google identifying me by my phone number. This is one of those situations where anonymity loves company.

Also, the problem is not limited to e-mail. There are some non-email services from Google. I'd be perfectly happy to sign up for a Google account where you can't send e-mails, or where you can only send e-mails to people who have sent you e-mails.