The problem is that the process of deletion of an inbox e-mail item in Outlook using IMAP is configurable and the behaviour also depends on the provider of mailbox.
It is well described here.
There are two types of behavior that can be configured:
Messages are marked for deletion:
Messages marked for deletion are
displayed in strikethrough text and are not moved from their original
Deleted messages are moved to a folder that you specify: This is
consistent with other account types in Outlook and with deleted items
behavior in other common software. It also helps give better results
when you access your e-mail account using other e-mail programs.
To change what happens to deleted items in your IMAP folders:
Account Settings, and then click
E-mail tab, click the IMAP account that you want to change, then click
Change and then click
Deleted Items tab, do one of the following:
a. To have deleted items moved to another folder, select
Move deleted items to the following folder on the server and then click the folder
that you want the items moved to.
b. To mark deleted items but not move them, select
Mark items for deletion but do not move them automatically.
So you probably configured Outlook the 4b way (instead of 4a that corresponds with your phone's settings) and the items have been marked for deletion & not moved to the Outlook thrash folder.
The above is valid for Outlook 2010, Outlook 2013 takes care to autodetect the trash folder, so you cannot chose it yourself. In Outlook 2013 you should uncheck the checkbox
Mark items for deletion ... and eventually check the checkbox
Purge items when switching folders while online. It might also happen that Outlook 2013 fails to detect your provider's trash folder - but in that case Outlook would have created a new folder
Deleted Items on your server and that did not happen, as you wrote.
If you use Google Gmail as an IMAP account, messages marked for
deletion are permanently deleted from their original folder but may
still appear there in strikethrough text. These messages are still
recoverable because a copy is kept in the Gmail Trash folder.
You may also check your account using other methods like web interface to see if deleted messages are by any chance in a trash folder that is not visible using the IMAP interface.