What pre-iPhone devices had virtual keyboards? I don't know of any and Googling for them is not turning up much. I could imagine old Windows Phone OSes had some kind of onscreen keyboard which I would guess was pretty bad.

Apple themselves positioned the iPhone against devices with physical keyboards: https://i.imgur.com/hXtRmbG.png

I would argue "decent virtual keyboard" is an oxymoron :)