In Nintex workflows, some of the alert emails were failed! Further investigation found this issue happens only on notification emails with attachments of 1 MB+.
Moreover, There was a event logged in Event Log: System.Net.Mail.SmtpException: Exceeded storage allocation. The server response was: 5.3.4 Message size exceeds fixed maximum message size.
Checked the Exchange Server Message size limits, It was 20 MB but still unable to send mails with 2 MB! After a bit of googling, found the issue: SMTP Server settings.
After increasing the Message Size & Session Size, everything turned good.