The results are in: the best way to use webcams between a Windows and a MacOS X machine is Yahoo Messenger.
MSN Messenger does not support video on MacOS, ICQ does not seem support video at all (easily at least) and the open-source solutions are not stable enough yet. Too bad, as I was quite happy with Gaim.
Audio didn’t work so well, though (didn’t investigate too much why). Using Skype for this.