I use to talk with windows users and Skype is okay but it doesn't support webcam. Ekiga has problem with windows user (I had a problem)...
I found a http://www.phrozensmoke.com/projects/pyvoicechat/
Anybody know this application?
my friend used the msn webcam support in kopete the other day, and surprisingly it worked. dont know how well it works both ways, but you might want to look into kopete and see what it supports.