I don't know if this is an issue.... I use Ximian Evolution to send/receive messages and when you press delete it also puts a line over the message. To really delete them, we have to go into "Actions", "Empty Trash" in the toolbar. See if there's any option like that
. Also, ximian evolution is a great tool. It's also shipped within RedHat 9.0 CD's. Perhaps you would like giving it a chance.