Just a basic comment: Outlook is well known for its bad IMAP support.It is really not a recommendable IMAP client. My experience is similar to yours: it may work, then it may not work, while other clients can use the same account without problems. Essentially I think Outlook always beleives what it has on-disk for the account rather than believing the IMAP server, which leads to very strange situations. The issue you describe could be related to this.
Regards, Jakob
