I think the think that the one best meets what you want is a Psion 5MX.
The PocketPCs doesn´t have that formfactor anymore except for the Jornada which is both expensive and outdated by now. Not to mention battery life.
There is some new PocketPcs with 640x480 screens some even has USB-host so you could hook-up an external keyboard.
A Bluetooth-keyboard is another option if you want a real keyboard for PocketPCs.
I don´t like the built in recognizers in WinCE, I replaced it with this
http://www.phatware.com/calligrapher/index.htmlit´s simliar but better.
Of course the Newton Messagepad 2000 has the best handwriting recognition. If you can find one secondhand go for it, it´s the best PDA ever. There is keyboards for them to but I never needed one.