Call to sysmail_delete_mailitems_sp keeps deadlocking
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!