Oh Outlook how I love you. I had a brainwave about the weird imap sync issue, where Outlook sometimes believes it has a folder on the server containing lots of messages, which isn't actually there.
I wondered what happens if you then create the folder on the server and sync again.
Answer: rather than deleting all the local messages to match the server, or uploading all the messages to match the local copy, it's done a bit of both, and now 75% of the messages are on both, and 25% are on neither.
And it's the 2016 version too, not just 2013, which is a useful thing to learn now but still a nuisance.
More detail on our work blog:
http://itservices.eng.cam.ac.uk/blogs/2015/11/imap-issue-still-affects-outlook-2016/