What type of account is it in Aqua?
POP3?
Please long press the account in Aqua -> options and folders -> account options -> enable "Remove deleted messages".
To go in the other direction:
For a POP3 account, moving messages to Deleted does not affect the server until you purge the folder.
To do this:
- Long press (the folder) in Aqua, choose Delete all.
Easier way:
- Menu -> Empty local [ Deleted ] in the account list
Automatic:
- Aqua settings -> mail, other -> enable "Purge [ Deleted ] on exit"
This should make Aqua actually delete those message from the server. The rest depends on your Outlook setup, of course. I assume it a has a setting similar to Aqua's "Remove deleted messages".