I had the same problem. After three days of googling, I discovered on reddit that this is happening to a bunch of people:
Here's what worked for me:
1. I found my host email server address, which is mail3.[hostingservice].com
2. I then went into Gmail settings and changed my SMTP server from smtp.[domainname].com to my host's email server name as follows:
- Settings > Accounts and Import > Send mail as...
- inserted my alias email address
- unticked "Treat as an alias"
- clicked Next
- entered my SMTP email server address: mail3.[hostingservice].com
- then carried on with all the other steps
- I was then able to verify my email alias
SIDENOTE: After doing the above, when I first went to send a test email from my alias, it didn't work. The email just hung when I pressed SEND. However, this may have been because:
a) just a few minutes before, I had renewed my Let's Encrypt certificate (because I wasn't sure before doing the above whether it was a certificate problem), and
b) a few people were reporting that Gmail was down on downdetector.com in my area.
So I gave it a few minutes for the new SSL certificate to cache, and did a full shut down and restart. (Yes, basic I know, but I am not a techie.) Anyway, whatever, I can now send emails from my alias again. Hurrah!
Thanks to everyone on this thread - your comments helped me eventually work out how to fix this problem. I hope this helps someone else.
Stay safe and well everyone!