the official ICQ clients do store buddys on the server, I think it's a pretty recent feature, but I don't know of any unofficial clients that do this :)
Smigs
Use AIM/ICQ, it uses the Oscar protocol which ICQ converted to sometime after aol purchased it. The old ICQ protocol (the ICQ plugin) still works but is unreilable at times.
Smigs