I seen k750i earlier today, and no, I do not want that beast. It is _Sony_, and that means memory stick (I already have almost _all_ the other flash cards). Furthermore, they changed conectors, rendering my charge-ericsson-from-usb (handmade :-) and small-qwerty-for-ericsson accessories useless. Plus menu animations are just plain ugly, and they moved volume setting to the wrong side of phone. As I use volume toggle to type quickly without t9, that's quite a big deal. Oh and still no EDGE support.
Other suggestion was treo 650, then force linux on it. I agree that GSM/GPRS shoudl be easy -- in fact I hacked gomunicator a bit, hoping one day I'll have a linux phone -- but powermanagement is quite a big deal, and cellphone without powermanagement is unlikely to be too useful. Plus treo looked big and fragile to me. I already carry Sharp Zaurus c-3000 with me, and this would be another brick. Okay, if I see something cheap-enough, second hand, I guess I'll go for it, but IIRC it has no EDGE and definitely no UMTS support.
(Hmm, and still collie + bluetooth CF + nokia 6230 or something like that should be easier to get to work than treo, with almost same benefits. Actually with more benefits as you can still call/do email/browse web from 6230 when collie fails).
Oh and actually k700 *has* search for address book, just press down, then start typing. If you type quickly enough,it will do kind-of-isearch.