[cd34]

Skype has chat (and is encrypted)

I had the same problem with icq a few weeks back -- however, I couldn't find a list of alternate login servers. But, I couldn't log into icq's web site and manage my account, so, I doubt I could have logged in even with a separate login server.

However, you can always use icq2go from their site IF you can log in on their server. Has a flash or java embedded icq client.