I have been researching various programs for video conferencing. most solutions are based around SIP which does pose unreasonable demands on firewalls for now. maybe one day, when we have wrestled back the end-to-end principle. more specifically, when SIP proxies are widely available and are easy to install. in the meantime, here is a list:
working

• skype (uses not firewalled nodes as proxies, but is audio only)
• eyeball chat (uses anyfirewall technology)

not working

• msn messenger (requires UPnP)
• aim 5.5 (requires to open special ports)
• paltalk (adware)
• ispq (requires to open special ports)
• ivisit (requires to open special ports)
• dwyco cdc32 (requires to open special ports)
• iChat AV (requires to open special ports)
• ICQ Video (requires to open special ports)

i'll update the list as i investigate more applications. note that i only considered free solutions. there are quite a few subscription-based solutions, not sure about their firewall traversal abilities.