I come across this often where the auto-clean rules don't touch emails sent or deleted from say an iPhone because they have a different folder name structure. 

Propose either making Deleted Messages and Sent Messages as items in the folder drop down for auto-clean or if possible just include those folders as part of the default Deleted Items/Sent Items rules if those folders exist.