I've done a lot of work with mobile computing and in particular the Pocket PC phones - I currently use an iMate and am waiting on the arrival of my HP iPaq 6365 which is coming from Singapore by way of a friend who is passing through, later this week (HP Australia are not releasing them until November/December).
There are a number of applications that I've found indispensable in my use of the mobile device that I feel are must have applications.
spb Pocket Plus - is a plugin that enhances the Today screen on the Pocket PC and allows a host of new features such as the ability to quickly close down a specific application, a battery monitor that runs along the very top of the screen and not take up valuable screen real estate.
spb GPRS Monitor - is a cool utility that allows you to monitor the traffic on your GPRS connection. You can punch in details of your GPRS data plan and it will track how much it's costing you and alert you if your over a certain percentage of your daily or monthly quota. It can also produce graphs and export information to a file for later analysis. Great tool that ensures you don't run up excessive GPRS data bills.
spb Time - is a great little clock that can act as a screen saver so that when it's in your devices cradle, it can be a nice looking desk clock. It also has a world clock that visually shows you night and day over the entire world map. I find this so useful as I communicate constantly with people across all timezones and it helps ensure that I don't call them in the middle of the night.
Pocket Informant 5.21 - enhances the calendar, contacts and tasks functionality of the PDA with some major extensions. Tasks can now have nested subtasks, and Calendar appointments can now be colour coded, have easy to pick start/finish and duration times just to name a few. The search facility can search across all of the PDA's databases for a given phrase or word - very powerful.
So - I hope these are useful for you all - I certainly have gotten some great use out of them.
Oh - nearly forgot - you can purchase these from either http://www.handango.com/ or http://www.pocketgear.com/ - I've used both without too many issues but don't have a preference for either of them.