If it just suddenly started happening, it could be AV or MS issue. To test, switch to Database Mail Server and see if it still happens.
My memory is hazy but I think I have seen this before and it was caused by an odd character either in the subject or message itself which interferes with the notification. I'm probably wrong as this was a few years ago.
Run a trace using SQL Profiler and include errors in your trace. You'll probably see the problem right away.
I switched the from address in the message system settings from an individual's email address to one used as an alias and the emails stopped. I don't know if I would claim this one as resolved. Weird.