Email headers? You mean messages?
1 - Mail apps don't sync with each other, they all sync with a mail server
Aqua Mail <-> mail server <-> another mail app
2 - Therefore, please check web mail (your mail provider's web site) to make sure that the other email app really does delete messages from the mail server as you're expecting
3 - Finally, please long press on the account on Aqua's main screen -> options and folders -> account options -> make sure that "remove deleted messages" is enabled (checked).
If it's a POP3 account you'll also want to increase "messages to sync" to, say, 100 (from the default 50).
