1. I'll go with the flow and say always-on capabilities. A BIG plus when you're constantly out.
2. Just about all of them, but I do like verichat the best.
3. Verichat again
4. Yes, I've tried them on kyocera 7135, treo's and other mobile phones, and with the full QWERTY keyboard and always on it is much more superior to other devices.
NOTE: I wish one of these guys would develop some corporate IM support for their products. A GroupWise Messenger client would greatly enhance our organization.