It's easy to search encrypted data, you just decrypt it first.

What makes you think Google would be reckless enough to store unencrypted private data on disk, or incompetent enough to not implement search over an encrypted set of data?

My suggestion was to encrypt the data client-side and store the accounts encrypted, so Google couldn't themselves decrypt the accounts. The purpose is to think of ways to structure the technologies so the hosting providers don't have to be trusted entities.

That doesn't work, as anyone providing you a clientside cryptosystem can provide you a backdoored clientside cryptosystem at the government's demand (one that silently uploads your key material to the server).

It doesn't matter if they don't normally store the key. It's a webapp.

Also, they need the key to do search. Furthermore, this does nothing to hide the metadata surrounding your communications, which necessarily must not be encrypted for services to work.