My e-mail server is in California and my correspondence with it (I'm in the UK) is encrypted also. Where are these countries drawing the line? Who would the British Government come after? They can't go for the ISP as that would cut my service off completely. They can't go after the Californian server. That leaves the only option of purloining my phone to ascertain what my e-mails are saying.
If private individuals can do this easy as pie and the terrorists are likely doing the same, (I can't see an enemy of the US using a US service for their communications.) then why are the governments chasing Google, RIM, et al? I can't understand why they don't simply face up to the fact that technology has given the individual citizen the ability to communicate outside their all reaching eyes.
I don't think terror is really at the heart of this. My own belief is that the Internet gives the people control over their government and they don't like it; particularly those which rule their population by religious fear.
This isn't protection against terrorism, it is government unable to control their population.