When I had messages stuck in the Queue...

I tried stopping with sysmail_stop_sp and then starting with sysmail_start_sp. Both commands completed successfully, however, the items still remained stuck in the queue.

I then noticed in the Windows Task Manager, the DatabaseMail.exe process would not disappear when running sysmail_stop_sp. I then killed the DatabaseMail.exe process in Windows Task Manager, then ran sysmail_start_sp, and boom, messages started flowing again.

I hope this helps as it took me about 5 hours to get here!