It's seemingly a known problem of Outlook:
https://support.microsoft.com/en-us/kb/2231628
However, the fix offered by Microsoft is really too much complicated and hard to follow. In my case, since on my mobile device and web mail the emails are good and the latest, the simplest way to fix it is to go to the Account Settings on my Outlook desktop application, remove the account and re-create a new one.
I'm using Outlook 2003, if you're using a different version, principle the same:
Go to "File", press the "Account Settings" button, choose "Account settings...". Under "E-mail" tab, select the email account having problem (in my case the Hotmail account), press "Remove" button.
Now, restart Outlook. Again, go back to the same "Account Settings" page. Press the "New..." button and step by step setup your email account again.*
*if you've started 2-step verification, likely you have to go to your Microsoft account (web page), and under "Security & privacy", "More security settings". Click on the "Create a new app password" and use this password for Outlook application to connect to your email account, instead of using your normal Microsoft login password.
Once account settings completed and good, all your emails will be back.