A la primera pregunta te respondo que si hay otros messengers muy parecidos al que casi todos tenemos, que funcionan prácticamente igual. Yo he provado el amsn messenger, que principalmente está hecho para un entorno linux, aunque hay una versión (al menos) que funciona en windows. Lo puedes descargar en este enlace:
Amsn-pack-0-90.exe
Su página principal es:
http://amsn.sourceforge.net/index.php?newlang=spanish
Si tienes problemas sobre como instalarlo entra en:
http://www.faq-mac.com/mt/archives/003948.php
Sobre tu segunda pregunta, a no ser que tengan un programa para controlarte las páginas que visitas o algo así, lo que puedes hacer es borrar el historial pulsando en la ventana del explorador "Herramientas", "Opciones de internet", "Borrar historial". Si hechas un vistazo a la ventana verás que puedes borrar también cookies y archivos. Supongo que borrando estos dos últimos ya no habrá ningún rasto en el ordenador, exceptuando si tienen un programa a parte para ello.
Espero haberte ayudado, auque no soy una experta en el tema.