Usually but some people have problems with it. Might be their own fault not forwarding ports and whatnot but I haven't heard too many problems with Skype at least.
I have tried video conferencing iChat - AIM on Windows XP many times and it only worked once for 10 seconds. Skype is the best for x-platform video IMO.