And not Google's fault at all. Mail wasn't connecting to the SMTP server and failed to notify me that it was happening. At root of the issue was Mail's use of the email password in two different places, with two separate copies of the password.

All I had to do was enter the password again. The same thing could happen to anyone else who changes their email password but only updates it in one place in Mail.