XMPP is an open protocol. There are encryption extensions. Gtalk is used for routing, so it's route-around-able if you have concerns about snooping, still letting you communicate with grandma's gtalk account who doesn't have concerns about the FBI. This is much harder to do with software like Skype (especially considering the obfuscation that has gone into hiding the operation of the Skype code).

An you can't have pay for service like calls to 'real' phones because if the billing was done in the client you could simply remove it, forcing all the billing to be done at their servers - which makes it much more expensive.

You mean like how land lines and cell phones do their billing on the provider's servers and don't do the billing in the phone itself because you could simply remove it?

Search engines are completely different from downloaded software - you can't avoid reliance on the provider unless you feel like writing your own web crawler and waiting for it to gather web content (even though it will never catch up with the volume of new stuff constantly being put on the 'net).