I know this is an old post, but I wanted to add this since lately we have been dealing with few failures of SQL Mail not sending email.

1) If EXECUTE dbo.sysmail_start_sp does not work, then go to task manager and stop/start the databasemail process. The process name is DatabaseMail.exe. Once you started the process, send test mail using the profile(s) you have to clear the unsent mail queue.