Messages moved from Inbox don’t actually move, on the Exchange server

I connect to an Exchange server with Microsoft Outlook 2011, and Apple Mail, both running on several Apple machines (OSX 10.8 and 10.9). On two of those machines, when I move messages from Inbox to other Server folders, with either application, they stay moved - disappear from Inbox, appear in the folders, all fine. But on my laptop, the weirdest thing started to happen. On both Outlook and Mail, the messages seems to move, but then either 1) shows up again in the Inbox a few minutes late (this is on Apple Mail), or 2) looks like it's moved, but other clients (as well as OWA) shows me that it's not in fact moved and is still in Inbox (this is what happens with Outlook). It's like those client applications can't convince the server to actually move them, but why is it both of them, from that one machine? I know they both connect to the server ok because I can receive and reply to emails. How do I debug this - how do I figure out why that one machine can't seem to push message move commands no matter which client is used?