Hmm...Clies...
One of my main problems with the Clies is the Memory Stick factor. Actually, come to think about it, that's my problem with a lot of Sony products. But you mention memory stick compatibility in something you
want in your handheld. If that is the case, then you really have to go Sony.
Just for comparison, the
Tungsten C has a lot of what you want (keyboard, twice the RAM you ask for, 802.11b, etc.)
PocketPC is a completely different world, but I should tell you before you decide to stay away from them, that they are not as heavily priced as you seem to think they are (compared to what any clie with the features you described would cost, that is).