> But wouldn't these circumstances ultimately mean that every service that holds information that could somehow be interesting to the NSA would have to shut down pretty much now to avoid exposing customers/users?

This is exactly what Lavabit owner hinted at in his statement. I don't remember the exact quote right now but it was basically along the lines of 'don't trust your private data in any US-based company'. And yes, the NSA can go to any company in the US and request private data while simultaneously putting a gag-order on them. You can bet Google, Facebook, ect have been victims of this many times before any of this came out to the public.

The problem is these multi-billion dollar companies aren't going to give up everything they have because the government is requesting information and keeping it hidden from the public. They quietly share the data and hide behind the gag-order, which is why Lavabit owner has some serious guts and should be commended for taking on the US Gov.