Call to sysmail_delete_mailitems_sp keeps deadlocking I run SQL Server 2012.
I have a maintenance job that runs every night. At the end of the maintenance, I do some cleanup and call this: 

Begin try
Exec msdb.dbo.sysmail_delete_log_sp @logged_before = '20160613';
EXECUTE msdb.dbo.sysmail_delete_mailitems_sp  @sent_before = '20160613';
End try
Begin catch
-- Do some log error
End catch

I put the transaction in a Try/Catch but it doesn't seem to be working. I keep getting this error : 
"Error 1205, Severity 13, level 18 : Transaction (Process ID 112) was deadlocked on lock resources with another process and has been chosen as the deadlock victim. Rerun the transaction."

If I run the transaction manually, it runs fast and I don't get any errors.
Any ideas why I keep getting this error or how I can catch it so it doesn't fail my job?
So I didn't got any luck with the deadlock graph. Doesn't seem to appear in my SQL Logs. But, I did find out that another job has been scheduled to run at the same time than my job, and it was taking backups and sending e-mails at the same time that my job was trying to cleanup the mail history.
So changing the schedule of the other job got my problem solved!