Inbound private (not Google) mail server that GPG's message subject, hashes addresses, GPG's original body & addresses, includes hashed keywords alongside GPG'd stuff in body. Forwards to Gmail.
Javascript on top of Gmail that decrypts GPG'd payload and hashes search box input for searching.
Javascript on top of Gmail that GPG's addresses, subject, body, etc. for SMTP server & user key. Also adds hashed search stuff. Private (not Google) SMTP server decrypts all components, strips hashed search stuff and sends out mail plaintext.
That's all just shooting from the hip, crazy?