This is not normal behavior for a standard IMAP configuration. I would begin your checking your account settings within Outlook.

You can access your account by select Tools > Account Settings.

1. Select Your gmail account and click change or edit
2. Select More Settings
3. Under the advanced tab, check to see if Remove from server when deleted items are deleted is selected.



If it is not select it and attempt to remove your deleted items again.

Hope this helps.