Mit dem verzögerten Löschen vom Server hast du allerdings eine meines Erachtens sehr brauchbare Zwischenlösung gefunden.
Der Nachteil bei diesem Vorgehen ist allerdings, dass der Status der Mails (gelesen, gelöscht oder verschoben etc.) auf den unterschiedlichen Abrufgeräten nicht synchron ist.
Grüße Basti