Thanks for the replies guys. It's weird, but it doesn't seem like the folks at HoFo are very helpful. Everyone seems focused on phones, and not as much on handhelds.
Ludites!
Interesting notes on the carrier situation. I knew you'd have insights Bob.

I'll def have to do some more investigating and check out Sprint. One thing that pissed me off about them though. There's apparently a wireless card out there that is rumored to work with MBP's via a driver some random guy wrote. I'm a little nervous about trying it though. I talked to a few different Sprint CSRs and they all seem to be programmed to shut down when you mention the word 'Macintosh'!
I've also read on a Mac forum that unfortunately a Win device would be better for my tethering set up. Isn't that bizarre? Mac users pimping M$ stuff! I'm not crazy about PPC's. at. all. Though I think I could be convinced (cough: Alex).
As far as sim cards go, I usually swap my sim once I get where I'm going, which in the past has only been random travel. I think I might invest in a
United Mobile sim (formerly Riing) which gives you a Lichtenstein phone number that is accessible all over the world. The outgoing rate is typically .39 euro for international roaming, no matter the country. This is obviously much better than $1/min, not to mention having to give out a new number every week! The only thing I don't know, like minimalposter points out, is how/if it works for data.
We're not a horribly big company, which has its advantages and disadvantages. We have a corporate account that gives us a pretty good deal with TMo, but I'm also free to do my own thang. TMo doesn't readily support Treos afaik, which isn't a huge deal, but that means that I won't get a bargain price out of them.
If I find out more, I'll ring back (tee hee). If I wind up with a functioning pcmia card, it may just be that I wind up dividing the kitty and having my phone and my computer on different networks.
My deal is that I like to get value for money. So I do fun things like piss off the travel agent by finding better/cheaper flights and hotels that cut into her commish. It might be a disease.

Anyway, I'm trying to find the best dealio with a device too, though it's starting to become painful.
The search continues...I'll let you know where I land. If anyone has other thoughts, shout please.