wndshr,
I am airline, and ended up with Nextel for my service. Most of my Int'l trips are 3 days or less so generally I don't call home but I did want something to be available for emergency of important stuff. (3 young kids at home).
For me it came down to T-Mobile or Nextel. Sounds like Gulfstream 200 likes T-Mobile. When I looked, they had some coverage problems in the USA, but that is just what I picked up from internet searches. He is probably a better source than me.
I'd check the likely places you fly to and pick who has the best coverage.
http://www.nextel.com/services/worldwide/index.shtml has a list of it's service and coverage. The phone choices are somewhat limited. I have the I2000 plus phone. the great thing about it is that it is a dual band phone that works in the USA and abroad with automatic switching. In Brazil, call your 7 digit local USA phone # and it rings there. As reported, the sound quality is phenomenal and better than on their USA cell system. I use it rarely abroad, but the first time I took calls walking around London, both callers busted out laughing. They literally sounded as good as calling your next door neighbor on a landline, and I had picked up on the second ring. Must be undersea fiber optic, satellites have a delay that makes talking somewhat odd.
The I2000 plus is a plain, functional battleship grey phone. It's not the smallest, but the ladies aren't impressed it's in your pocket either

If you want to download Village people ringtones, send color instant pictures of your decorating or play games on a phone, it won't be the one for you. It does do about everything else though.
The great thing is that with this phone and a regular Nextel US phone plan, there is no charge to activate the International service. You only pay if you use it abroad. Cheapest is the UK at around $1.20 minute up to places like Brazil at $2.40 minute. Not cheap for yakking but good for emergencies or in my case calling crew schedule for an extra trip for extra $$$$.
The phone is also a SIMM card phone. It has the little standard removable plastic computer chip in the back. I haven't done it ,but I know a flight attendant who bought a UK Orange prepaid SIMM card for about $75, then swaps it for his US card then calls home for 20 cents a minute, and has a UK cell number for calls from home at 8 cents/minute. These things are worldwide and very common. You may have to get the phone company to give you a code to "unlock" your phone to do this.
Look on the internet for GSM or some site like "GSM World". That's the basic system used around the world except the US. the site I saw had all the websites for prepaid SIMM cards and roaming agreements.
Hope this helps, I went through the same search last year.