Just reread the above and realized it made no sense....
I, too, have the same problem, in that I access my mail on two different machines, and oftentimes what I delete on the house machine (at least I thought I had deleted!) shows up on the office machine.
It's like the server didn't realize that I deleted the mail. So, I've taken to doing the select all (in the trash window) and delete instead of empty trash. I also don't quit the mail client right away, it seems to take ±5 minutes for the server to recognize the command. I blame it on Bernie no, really, I blame it on the "leave messages on server" but that is a necessary evil.