I know this this is an old thread, but thought this may be worth a mention.
I have the same issue on a SQL2016 / Windows Server 2012R2 box.
I'd tried everything (up to and including deleting and rebuilding the mail profile!).
I finally got round to checking Task Manager (thanks to Isalih for this one) and noticed that I'd got 2 instances of DatabaseMail.exe running.
I killed them both, stopped and restarted mail in SSMS (using EXEC dbo.sysmail_stop_sp and EXEC dbo.sysmail_start_sp) and all is now good.
Hope this helps someone.