Removing IMAP mail on iPhone not visible in Outlook trash
Make sure that the messages are not being trashed into the generic mail trashcan on the phone. The need to specifically be trashed in the IMAP account's trashcan.

Go to Settings > Mail, Contacts, Calendars > (Your IMAP Account) > Account > Advanced > Deleted Mailbox and make sure Trash on the Server is selected. Not Trash on the phone.