Gmail rejects mails with “email account does not exist” for active accounts

I experienced it today and searched twitter. Looks like a lot of people have this problem:

https://twitter.com/search?q=gmail%20account%20does%20not%20exist&src=typed_query&f=live