In terms of PocketPC vs Palm, that pretty much comes down to personal preference. FWIW, I used a PocketPC for over a year, and ultimately tossed it in favor of a Palm. Reasons: stability woes and paltry productivity-related software. You might want to check out the GTD groups at Yahoo- one for PocketPC and another for Palm. Run a search for GTD at the groups home page.
As regards paper vs device, I find that I'm much more consistent with the PDA. First, there's a fun factor involved, which inherently encourages me to carry it with me wherever I go, which means I have **ONE** thingie with me, which means I use it, which means I can always FIND stuff when needed (my PostIt notes had feet!!). Second, I no longer hassle with the sloppiness coerced when moving an uncompleted item from one day to the next; or spend time re-entering annual dates year after year. Third, I can answer virtually any Q within a matter of seconds. Examples:
-- free time this month = one-glance at icon-driven month view, as the icons immediately tell me the nature of the whatever on a given day (desk/in-office appointment vs phone/series of calls to be made on a given day vs lamp/research required vs car/be somewhere that day.
-- due dates whether today, next week, this week, within 10 days, etc, at one glance
-- EASY movement of, say, a someday/maybe item from that list to an active project list
-- auto-logging of what was done when
The list goes on and on. Suggestion: go to a local, say, Circuit City store, and literally play around with a few models on display. If you get one, you'll have 2-4 weeks as a trial, as they have a no-Qs asked return policy. Be conscious of size-- no one wants to carry a brick everywhere. Personally, I like keyboard-based PDAs. You may prefer one without a keyboard. No one can tell you what's best for YOU. So try, have fun, and perhaps check out software reviews at various spots.
Finally, don't think for one minute that because a PocketPC has the MS OS that it will be a better fit for your MS desktop programs. Outlook and other MS apps are frequently better accommodated on the competitor's platform.