I can appreciate the not deleting unless explicitly set to thing, but it seems strange that something like Outlook online has no obvious setting that allows you to say "delete from server when deleted in Outlook"...unless I'm being a numpty and I'm not setting the server settings up correctly.
Bluemail seems to work reasonably well, the clusters has helped speed things up a bit though it's a bit hit and miss as to what it decides to group together!
you may need to purge the folder to delete them off the imap.
take a look in your account settings & more settings. There is deleted items