So, you had this before:
Old PC with Office 2003 <-> Office365 <-> Galaxy S4
and it worked, but now you have
New PC with newer Outlook <-> Office365 <-> Galaxy S4
and it doesn't work.
If that's correct, it sounds quite weird. Office365 shouldn't interact with your phone any differently just because you updated to a new PC client.
What happens if you connect to Office365 webmail? I suspect you will find that your deleted mail is still there, and it's only deleted on Outlook. It shouldn't be able to happen that way; it's not like POP3 where the client can choose to leave deleted messages on the server or not, this is all server-based.
First try clicking the Send/Receive All button.
Sometimes Outlook has difficulty keeping a good connection to the server, and it seems to only have gotten worse in newer versions. You can check connectivity at any given moment by holding the Ctrl key and right-clicking the Outlook icon in the system tray (the small icon right next to the clock in the bottom right), then click "connection status". If it's imperfect, go to your account settings and edit them as described here:
Configure Outlook 2007 or 2010 to work remotely using HTTP
Especially try toggling the two "connect using HTTP first" check boxes this dialog box: