In fact, I recently shut down a personal App Engine service I had been using for myself for a few years just because of this paranoia. The service was not doing anything illegal, just crawling a few websites (forums, ...) I like and sending me emails when there are interesting updates. But you never know if they might determine my outbound traffic is suspicious. I also started the long process of moving my main email from a @gmail.com to a @custom.domain that currently forwards to gmail, just in case I get locked out.
It is quite bizzarre that this is the reputation google gained for themselves.