Turn out when I logged into the Server with the service account, I was prompted with a dialog for Symantec PGP which want to encrypt all mails. I configured this to not encrypt all mails and everything was back to normal.
Check SQL Server Agent Properties: on the "Alert System" page, is "Enable mail profile" checked?
Sometimes with new installations, after I set up options on that page I've found notification emails for alerts aren't sent. A restart of the SQL Agent service often addresses that issue for me. - dave-mason
An article that explains more details: How to setup ...