One more thing to check: that the app's "deleted" folder is properly "mapped" to the right server folder.
Please long press on the account -> options and folders -> folders.
Let the folder list refresh from the server (5-15 seconds).
Find the right Deleted folder (may be called Deleted Items, Deleted Messages, Trash, Bin, ...)
Tap its name.
Choose "Sync as Deleted".
---
The above procedure "tells" Aqua Mail what server folder to use for its Deleted folder.
If there isn't any, the app's Deleted folder will be purely "local", won't sync with anything. Sounds like you case.
---
Oh and if your account is set up in Aqua Mail as POP3 - this won't work because POP3 does not provide access to folders other than Inbox. I'd recommend removing the account from the app and adding back as IMAP.