There are many options... you say from the Deleted Items folder? Go to Menu, Tools, Empty Deleted Items... and that should do the trick.
Also, this app is awesome... it adds 2 options to your POutlook Menu, Mark All As Read and Delete All...
http://forum.ppcgeeks.com/showthread...=mark+all+read