I've only been using a palmpilot this year and have used it for practically everything, from organizing my uni timetable to taking lecture notes. With the latter, it was hard to keep error free notes using graffitti as there is a large margin of error even with Tealscript. My ideal situation would be to take the notes on my Palm and save me from having to type out my hand-written notes into my computer.
I only started using the Fitaly stamp when the competition had started. I was pretty slow at first, but found that my speed improved if I rested the palm pilot on a flat surface, used one hand to steady it and rested the tapping hand while tapping instead of having it hovering around looking for the next letter. There's more accuracy and speed in just moving your fingers than moving your entire hand and arm when tapping the stylus about. When I'm without a flat surface, I tend to lean my hand on the bottom left hand corner of my Palm pilot to stabilize my hand and let my fingers do the work.
With everyday use, I've found that using the game mode and trying the 'train' words to be helpful in improving my speed especially when words that are used often come up (eg the there when went also). I'll have to try that 'quick brown fox...' suggestion of Ken's.
As for that fast time - well, that came with practice, and just 'knowing' where the next box I had to tap would be (this includes the nearest spacebar!). Also, I had to concentrate on the accuracy of my tapping until it became second nature. I also found it better to tap lightly, as it gave more speed so that my stylus became a blur over the Fitaly stamp!