I set up my email account using IMAP4 rather than POP3. When I've deleted a message from the PPC if I click send & recieve it will then delete it off the server too.
IMAP4 also supports directories which is very useful.
The golden rule is click send & recieve after deleting or moving any message. This will update the server.
Also in the options somewhere you need to select "delete messages immediatly" from the drop down menu.
Hope this is useful.
Shameless plug: If your email account doesn't support IMAP4 we can rent you one that does for £12/year + vat
