Non c'e' una risposta semplice, dovresti diagnosticare un attimo il tutto.
Generalmente, se i client scaricano gli stessi messaggi via imap o via pop3 (con l'opzione "salva copia sul server" on) significa che c'e' un problema con gli uidl.
Nel caso del pop3, quello di default su qmail prende gli uidl dal nome del file, e gli aggiunge un tag dopo la prima lettura, spostandoli dalla cartella new nella cur.
Nel caso del courier imap, c'e' un file speciale per gli uidl, in cui il daemon deve poter scrivere e leggere.

Quindi dovresti controllare che sia tutto a posto con i permessi come prima cosa. Se ti va bene, e' questo il problema.

Ma poi ci sono anche i bug dei vari client tipo microsoft outlook, con il format degli uidl.
Poi esistono quelli che hanno i vecchi outlook senza il hotfix che c'e' in un service pack di qualche anno fa.
Poi ci sono anche quelli che hanno il tempo di check automatico troppo basso e la connessione troppo lenta, e succede che mentre scaricano un messaggio, il client si collega di nuovo, senza aver finito l'operazione, e lo considera come nuovo.
Poi ci sono alcuni antivirus cretini che cambiano dei tag all'interno delle mail, facendo credere al client di non averli scaricati.
Poi ci sono quelli che hanno dei filtri malconfigurati, causando messaggi che si copiano in piu' cartelle. Poi ci sono quelli con i mailbox corrotti.
Eccetera.

In conclusione, se non e' un problema di permessi, devi debuggare tutto passo a passo. Buon divertimento