I think it is to do with your IMAP settings - see this link on how to set up the "Special folders", the bit after B. 6.
https://answers.microsoft.com/en-us/windowslive/wiki/livemail-email/windows-live-mail-and-outlook-mail/6edb5ba6-f9f2-40fd-80a1-fc23cc6fbfe0 - if messages are kept on server, you should be able to see them across devices. On the advanced tab you want the box checked to use Deleted Items for IMAP. Also, if you do not want to delete all Deleted Items on exit, make sure that option is unchecked.
If there is no IMAP tab in Properties, it is using POP. Set options on Advanced tab to leave a copy on the server.
If you change your settings, do a test with a new email to check it is doing what you want.
The advice from Microsoft for recovering a lost email is to access your email through the web portal, as it may still be there.
This forum may help in general
http://answers.microsoft.com/en-us/windowslive/forum/livemail?tab=Threads&auth=1