I'm currently also looking for a new phone. My need is slightly less drastic, but a bit of a change is planned. I've decided on an Android phone, but I've run into the same physical keyboard problem. Things I really like about my current E71 include the damn good keyboard. One possiblity might be Swype (http://swypeinc.com/) which I've been hearing good things about from another physical keyboard addict, and so I'm getting Alan to get into the beta and let me test it out on his Android phone. If that works out, I'm thinking about the HTC desire.