It sounds like POP if they have it set to leave copies on the server. I'm thinking it's an Outlook issue since POP servers are pretty simple and it's up to the client to remember where they left off. I don't use Outlook, so I don't know where to begin.
However, if one is going to want to leave copies on the server, why not just use IMAP? POP's not efficient with wading through messages on a server.