Concordo con te sulla necessità di salvare la posta già scaricata e quella inviata in un qualche formato facilmente accessibile e gestibile. Perché non usare un database.

Hai detto bene, non ha senso creare un database per ogni utente, anche se la cosa in sè non comporta molti problemi (che cambia connettersi a: database_posta_nome_utente) oppure fare query del tipo: SELECT * FROM messaggi WHERE ... AND id_user = user_loggato

La cosa invece di cui preoccuparsi, una volta risolti i problemi di connessione è la sicurezza dei dati... sarebbe poco simpatico che le email, rubriche e quant'altro venissero salvati in chiaro nel database.