If you download mails to your phone, quit the connection to your ovi mailaccount and the choose to delete the mails on phone and server.
They just get marked and are kept in your phone and on the server. There is no synchronisation afterwards and you have to delete the mails in the web frontend.
Nokia 5800 XM
V 31.0.101
Greetings