Ciao!
anche io uso Evolution, e ho anche io i miei problemi...
Ma riguardo al tuo, hai gia' provato a selezionare la cartella Trash (Cestino) e poi dal menu Actions > Emty Trash? Dovrebbe funzionare. In aggiunta, ti consiglio di selezionare da Tools > Settings > (apre il dialog) > Mail Preferences > (tab) General. Qui, tra le opzioni di "Delete Mail", seleziona "Empty trash folder on exit, every time". In questo modo Evolution svuota il cestino tutte le volte che chiudi l'applicazione.
Se non dovesse funzionare, potresti avere qualche bug, e ti consiglio di segnalarlo allo staff di sviluppatori, rivolgendoti a http://bugzilla.gnome.org/ . Devi registrarti, scrivendo il tuo indirizzo email, e riceverai una password che puoi utilizzare per cercare le informazioni e inviare nuove segnalazioni. Io ho provato il sistema ieri, ed e' risultato molto efficiente. Se hai bisogno di altre infos non esitare a chiedere!