A similar thing has happened with companies that go to great lengths to make sure they don't have any gender bias in their hiring process (no face-to-face during interviews, voice altering during phone interviews, etc.) only to find that they still selected more men than women. The conclusion, of course, is that they must be doing something wrong because it's simply impossible that they wouldn't be selecting a perfect 50/50 mix of men and women.
Similarly, I think imagine Google will find similar flaws with how these numbers were generated.
It's extremely difficult to actually hide all signs of gender, even with the measures you mentioned. Even simple things like the way a job advertisement or a resume is worded can suggest the genders of the people involved in a statistically predictable way. For example: http://gender-decoder.katmatfield.com/static/documents/Gauch...
Similarly, I think imagine Google will find similar flaws with how these numbers were generated.