I've had a similar problem before. I am guessing you are using POP3/SMTP and not exchange or something? Anyway what was happening with mine was that if a user was getting a lot of email say like 100 messages they would get doubles, triples and up to 5 times on some of the emails. What we figured out was happening was after Outlook brings down the messages it tells the server to delete all the ones it just downloaded (unless you tell outlook to leave a copy). Well, sometimes the user would get impatient and hit the send/recieve button again or after 1 minute in some cases outlook would go check again for messages. Because it was in the morning and the mail server was being bogged down by all the people logging in and checking messages sometimes it didn't have time to delete all the messages from the last time they checked. The way we fixed this was to change how often outlook checked for messages from 1 minute (or whatever the user has set it to) to like 10 minutes.

Let me know if this helps,
Greg

P.S. Every once in a while I still get a complaint of someone getting doubles but it happens so infrequently I don't really worry about it much, but would like to see if others have had this happen at all.

P.P.S Check and see if the clients have a way to check the mail via a webmail client or something. See if there are multiples of messages in their inbox there.