joshd, you really nailed the unfortunate reality that synchronizing with a PDA is a pain. I once had a lot of success using a Treo 600 for GTD, but I lived in that device, using it for all data entry and reference. I only synced with my laptop to back it up because it seemed that every time I tried to go both ways, I'd end up with duplicate entries, unexplained deletions, etc and I spent more time trying to hash out those problems than I did using the damn thing.

Merlin, knowing that you are a heavy kGTD + iCal user, I don't think you'd be happy adding a Treo to the mix. It's not even about the device itself, but adding any PDA means you have not one, but two sync steps (kGTD to iCal to PDA) and one more chance for things to go wrong. Believe me, I've tried it: I have a smartphone now and I tried out MissingSync, but the sheer time alone it took to get one to-do from kGTD to the device was maddening, not to mention the quirky mis-mapping along the way.

I've resorted to using the phone for its real strength, its networking, to do email, texting, web browsing, posting snapshots, etc, and do the rest on my computer. If I really need to take a list of NAs with me, I print it out or scribble it on an index card. For those purposes, I think you'd still like the Treo if you have the budget. It is a good all-in-one device and the form factor is great for banging out quick messages or even as a mobile inbox. But syncing? Bad news.