While I don't doubt volumes have fallen as a result of things like email, the US postal service also hasn't done itself any favors. You read anecdotes like this, and it's a wonder that volumes haven't plummeted even faster: http://www.theatlantic.com/business/archive/2010/04/things-a...
And I have equally aggravating anecdotes about issues with private companies' customer service. It doesn't prove anything. I'd take the people at my MVC (NJ's "new" DMV) and post office over the people at my cable or internet provider, my private healthcare, and my cell phone company in a heart beat. Those companies aren't doing themselves any favors but somehow they manage to make it. The Zappos in the world are few…
These aren't exactly archetypes of free market competition, being oligopolies, at best. I can't speak for NJ, but, in California, I consider it telling that they all have a state regulatory agency.
Number portability has improved telephony competition, but I don't think we're yet free of the effects of the old A/B cellular duopoly in the US.