I did the Google Talk + MSN/AIM/Yahoo thing, and it works pretty good, after the initial setup. I just wish there was a way to reconnect to the gateways without logging out of GT and back in again.
I've been waiting for an affordable way to IM on my phone for years. It's ridiculous how long it's taken to become available. It's also been a godsend on my BlackBerry because I've found my friends are reluctant to email me just to chat, even though that's what I got the damned thing for.