• FYI, I've implemented Database Mail on a lot of instances recently and I've never had to restart SQLAgent (caveat: these were mostly 2005, 2008 and 2008 R2 instances).

    Assuming you can receive a test message to yourself sent by right-clicking Database Mail/Send Test Message..

    1) Verify the the email account is associated to the profile you specified in the job 2) Check the your junk email folder or anti-spam system.

    I've been tripped up by anti-spam filters more times that I like to admit. The #3 IT question after "Have you turned it off & on again?" and "Is Caps-Lock on?" ought to be "Have you looked in your Junk email folder?"