I am far from an expert with IMAP but the general idea is that the emails are kept on the servers...
I believe however that for performance reasons a copy of them is kept locally and resynched with the content on the servers...
If you said that the problem was only with Outlook I would think that there could be a possibility that something got corrupted in that local copy but the fact that you are seeing this behaviour elsewhere make me think that you might be right about the problem possibly being with the servers...
I have a question though, on your phone are you using IMAP as well or POP3? POP3, at least of what I have seen of it in the past, can be pretty unhappy about not being the only one reading the emails, I wonder what would happen if one of your clients was using IMAP and the other POP3...
POP3 usually removes emails from the servers so they would not usually be available for IMAP but you can usually disable this...
You would not happen to have another computer on which you could try replicate your Outlook setup to see if you can replicate the same problem by any chance?
Good luck and have a nice day!