For a POP3 account, you'll need to not only delete messages in AquaMail, but also purge the Deleted folder (long press and choose from popup, or enable an option in app settings -> mail, other for the app to do it automatically when closed with Back).
The reason is that POP3 doesn't provide access to server side folders, so moving a message to Deleted in AquaMail doesn't change anything on the server -- until you purge the Deleted, and then AquaMail deletes all those messages from the server.
Using IMAP is another solution, and actually, it has other benefits (access to folders, read state and starred state sync between devices, etc.)