Oh, and I suppose it should work reasonably well as a phone, too. I mean, I do use it for actual, you know, phone calls every now and then.

You could run Jabber on a Nokia E90 (http://europe.nokia.com/A4346040) and the keyboard is supposed to be decent. What I like about my Nokia E61 is that (like the E90) is has WLAN connectivity, so you can do things like Jabber anywhere that you can find a WLAN. That's important in Europe, where you generally don't get unlimited data plans for phones, and it's also important when travelling to faraway lands where phone data access is prohibitively expensive. Cheers, Tony.

Week ago I bought HTC Vox (S710). It's relatively small (more like phone then PDA) and has keyboard similar to Sidekick.

It is running on Windows Mobile 6 so you can get almost any software for it, but usually you have to pay for it.

I use Windows on my laptop so I can use ActiveSync for synchronization, but I think that there is similar software for Linux called SynCE. But I have never used it, so I don't know how well it works.

And I like phone part of this device, it has many benefits over my previous and very old Siemens S45/ME45.

Windows Mobile: not if I can avoid it.

(Overconstraining the problem, am I?)

I can't find a wireless provider in the US that's carrying the Nokia E6x or E90.

The Treo was on my short list back when I bought the Sidekick, but they all appear to run Windows Mobile now.

Verizon currently offers the Treo 700p

Verizon doesn't support GSM.

Out of the five current Treo models, three of them run Palm OS (and one of those three, the Treo 680, is GSM).

I don't know if it has "decent email, Jabber IM, and a web browser that doesn't suck"; on my Treo 700p, I've never used email or Jabber IM. I've used the web browser a LOT, and I'm pretty happy with it. (I assume the web browser on the 680 is pretty similar to the 700p, although I don't know for sure. Despite the model numbers, the 680 is actually newer.)