Is it only happen with POP? There is a MS KB article for Outlook clients.
http://support.microsoft.com/?kbid=885870
I quick google search shows that in general this is a common problem with POP clients especially over slow links. Are these folks on dial-up?