In preparation for the trip to Spain, I decided to see about getting a prepaid SIM while there so I wouldn't have to pay Cingular's incredible roaming fees. That meant that I had to get the phone unlocked; if not, the SIM would simply refuse to work.
That process was easy. All I did was call Cingular customer service, tell them what I needed, and give them the Treo's IMEI number (a unique number assigned to the particular machine). They told me it'd take a few days to email me the unlock code. It was waiting for me when I got home. Whee.
There's a service that will buy a SIM and deliver it to your hotel in the Madrid area, and email you the number in advance. Get to the hotel, swap SIMs, and go. Nice and easy.