Skype does much better than that. AFAIK they can traverse NATs and firewalls that don't support UPnP; they can fall back to TCP if UDP doesn't work; if all else fails they have a network of supernodes to relay traffic.
I'm just saying that everything skype does can be done with OSS using open standards. That skype is in any way technologically superior is mostly result of excessive FUD campaigns IMHO. :)
The quality is high, it's highly accessible and it doesn't have an equal competitor. Even the instant messaging services that do voice and video are poor alternatives. It has also been used for several years by feature phones and smart phones - some as their main selling point.
Essentially, its a pseudo standard used by most people.
Windows: Delphi Linux: C++ OS X: Objective-C