Doch es liegt schon daran.
$rcmail_config['flag_for_deletion'] = FALSE;
... sorgt dafür, dass eine Nachricht gelöscht - und ggf. in den Papierkorb verschoben - wird und nicht nur das Flag zum Löschen der Nachricht gesetzt wird. Wenn zusätzlich Nachrichten nicht angezeigt werden sollen, deren Flag zum Löschen gesetzt ist, dann muss $rcmail_config['skip_deleted'] = TRUE gesetzt werden. Letzteres aus der Erinnerung; ich bin mir nicht ganz sicher, ob der Key wirklich 'skip_deleted' heisst, aber jedenfalls so ähnlich.
Nochmal zum Verständnis:
Normalerweise arbeitet IMAP so, dass beim Löschen lediglich ein Flag in der Datenbank gesetzt wird. Die Nachricht ist aber immer noch vorhanden (flag for deletion). Die Nachricht wird erst dann endgültig gelöscht, wenn der Expunge Link unter der Ordnerliste geklickt wird (enspricht bei Outlook dem "Entfernen" Symbol). Ein Verschieben der Nachricht in den Papierkorb wird bei einem "Expunge" nicht ausgelöst. Die Nachricht ist endgültig futsch.