I've read about this in a few different places. What is happening is that when you delete a message on your Treo, it won't sync with your PC until next time mail is received and AS on your Treo runs. At least that seems to be the case when using an Exchange server. Basically it's not a 2-way push. Have you tried using the option "Delete Items Immediately"? I've heard this will make it sync upon deletion, but I haven't tried it yet.
Hope this helps
