I used to use Dasher on my old iPAQ from 2004. For the first couple of weeks, it was only slightly better than the OSK. Then as its dictionary of my words (and my practice) grew, I could eventually use it at speeds rivalling a QWERTY keyboard, probably after a couple of months or so.
It also looked awesome while you 'typed'. Like some sort of bizarre arcade game.