schau dir mal licq und sim an.
Beide könnten es können.
sim ist ziemlich wie icq, hat aber einige macken(ich hab mal meine kopntakliste verloren...)
aber vieleicht ist das jetzt ja besser.
Ich glaube mit Kopete kann es auch was werden.
Ich nutze es auch für ICQ, kann aber momentan nicht sagen, ob es Deinen Bedürfnissen entspricht (habe hier kein Linux).