Passwörter auswechseln, und lang genug wählen sollte erstmal helfen, ein neuer Account wäre besser, ja.

Generell sollte man Tools wie ICq,MSN und co einfach nur meiden, es sei denn, ein Tool bietet eine Verschlüsselung mit an.
Kommt natürlich auch immer drauf an, WAS man über solche Dienste kommuniziert.