Teamspeak is another option, along the lines Mumble. There are others. It's a diferent concept from Skype. ONe person has to run a server. They choose who they want to be on the P2P network. Teamspeak is closed source.
Free SIP services are another option, but not easy enough for the novice who is in a hurry and just want things to work. Most people seem to use SIP servers operated by companies, not running the servers themselves. Some ISP's are selling pre-packed VOIP service (and some are deep inspecting every packet, lol).
Skype has the market now. It is ubiquitous. It's easy to use and works reasonably well.
But to think Skype will become the world's new default global communications channel, with MS in control, is just silly.
Skype is just a hint of what's possible, given today's bandwidth and a network that no one player controls.
MSN relies on central servers to broker connections, just like this does. It is not going to solve the problem you describe.
True P2P, via an overlay, where you and the other person(s) have a direct connection, is fast and reliable "enough" (otherwise Skype would not have been successful), but not perfect. Nor is store-and-forward (e.g. text mesaging) perfect either. But it is "good enough" for people to use it.
If I were really concerned about "lost messages", I'd prefer a direct connection as opposed to one that goes through a third party. It just makes more sense.
Setting up the connections is not the "magic". That is not a hard problem. It's been solved years ago.
First, P2P networks to not have to be enormous. Drop your assumptions.
They can be small, and separated. (Think VLAN.) A P2P network can be set up so that any peer can volunteer to be a supernode. (Skype doesn't let you choose.) There must be at least one supernode to get a connection started but it does not have to be a company. It can be you, so long as you have a reachable IP.
And the supernode does not have to forward traffic. She can just function to set up the connections. And she can do so agnostic to the traffic. She only keeps a table mapping MAC's and private, arbitrary IP's. The supernode can disappear after the connection established; it won't break established connections. If two nodes are behind the sane NAT, then the supernode can forward to traffic to get around this impediment. Setting up connections is not the "magic". There's no need for MS to be a (or should we say, "the") supernode.
The "magic" in Skype is the way they handle the compression, encoding and decoding.
That is where one needs to focus.
Setting up P2P connections (for small, segregated P2P networks), reliably, and without snooping, is relatively easy. You or someone else in your contacts needs pulicly reachable IP. All the code you need to connect, which is not much- quite boring for the complexity lovers, has already been written.
Code is written. Command line only. So not ready for you yet.
There are good application programmers (who are also competent cryptographers). But it seems, based on mailing list and forum comments, all the incompetent ones hold them in spite. One can only guess why.
MS using Linux to run their business. That says it all.
A company with more money than it knows what to do with, acting desperately to save itself from obsolescence.
Skype was flawed from the outset, being non-transparent (about how the network is set up, turning machines into supernodes withtout permission, and the encryption they use). It's all closed. Why? You can't verify it's well-designed. Now it's worse. Do I want MS routing my calls? Scanning every file transfer? Being able to peek at any video?
No thanks. That's not their role.
There are other true decentralised P2P Video/oiceOIP solutions. People now know that free calls, even video calls, through the internet are feasible, even without having technical knowledge.
Right now, use Skype. But it will not hold the market when more robust, flexible, decentralised, transparent services are ready for non-technical users.
Because they will be free. And Skype will not be free: the price you will pay, to a software company[1], is your privacy, at the least, and probably more.
1. No software company has a need to know such things. They are not the government, they are not law enforcement, and they are not defenders of national security. They are a software company. Who are they accountable to? It's just not a smart idea to let MS take this role. The potential for abuse is too great.
Free SIP services are another option, but not easy enough for the novice who is in a hurry and just want things to work. Most people seem to use SIP servers operated by companies, not running the servers themselves. Some ISP's are selling pre-packed VOIP service (and some are deep inspecting every packet, lol).
Skype has the market now. It is ubiquitous. It's easy to use and works reasonably well.
But to think Skype will become the world's new default global communications channel, with MS in control, is just silly.
Skype is just a hint of what's possible, given today's bandwidth and a network that no one player controls.