Se você usa gtalk pode usar o empathy ou o pidgin. Se tem conta no Gmail, pode usar o bate-papo por ele com suporte a webcam também, basta nas configirações do Gmail adicionar um plugin para navegador.
Protocolo msn eu não sei te informar em qual funciona. Se o empathy já tem suporte a ele.
O comum mesmo é o pessoal usar o skype.