I had the same problem with my O2 XDA2 in Thailand. After much pain and suffering I stumbled on the solution.
I tried manually selecting the network, but when I select the designated network (AIS GSM for Vodafone), after a delay it returns a message "Unable to register on selected network. Choose another network, or disconnect your data connection and try again." - note that there is no cable connected to the device when I do this.
THE FIX Take the SIM card out of your Pocket PC phone (mine was a O2 XDA2), and put it in another phone (not running Microsoft Pocket PC) - I used a Nokia. Turn the phone on, and it WILL REGISTER your SIM after a 2 minute delay. Once you can make a call, take the SIM out and put it back in the Pocket PC phone, and it will work!
Thankfully the bug in Microsft's software isn't in Nokia's.