See Facetime and iMessage.

If Facetime worked for just voice calls, and over 3G, everything would be perfect.

See Google Talk and Skype, both of which can do voice-only calls and video calls over 3G. It's not all perfect, though...

The problem with Skype on a mobile is that keeping a connection to their P2P network requires much more power than the usual push notification channel does. It's more expensive computationally and traffic-wise.

Google Talk, in comparison, needs less power, but the audio and video quality is just much worse (on my Nexus S with ICS). I also have fewer contacts in GTalk than in Skype. And for some reason, on many phones, there is no audio and video support at all.

Agreed. Over half of my calling is via skype or other voip service. The evolution is happening...but a clear winner has yet to be identified. Perhaps there will never be a clear winner...