It sounds like you're doing everything online when you mention the 'leave msg on server' option checked. Outlook can either do everything while leaving the data on a server, or download it locally before you do anything. I would recommend you uncheck the leave msg on server option unless you want the data to be accessible through all the machines.
If you want to be able to access the data through all the machines, then it gets tricky because you could inadvertantly be deleting the messagesfrom the server from one pc.
The other thing that could be happening is that once they're read they're not showing up on other pc's because 'only download new messages' is enabled. Unchecking this option if it's checked is also good practice, since otherwise there'll be mass clutter on the server sooner or later.
Hope this helps,
Chris