[gwu78]

Certificates could be initially delivered out of band, e.g., in person, or by postal mail. Perhaps in a printed format that can be scanned in.

But then there's no way of telling which postal mail is actually from Google, right? :)

[nwh]

We'll sign the out of band letters with their signing key to prove it's aut- wait. Chicken and egg problem.

[gwu78]

Or we could just sign the OOB letters, on company letterhead, with an ink pen.