Privacy International, een internationale beweging die strijdt voor het recht op privacy, heeft in 15 Europese landen, waaronder Nederland, klachten ingediend tegen Google's Gmail. Volgens de beweging schendt het plan niet alleen lokale wetten maar ook die van de Europese Unie. Europese regelgeving stelt dat gegevens niet langer bewaard mogen worden dan noodzakelijk en dat het inkijken van e-mail slechts is toegestane onder bepaalde, strenge, condities. Volgens Google voldoet Gmail aan de wetgeving, maar het bedrijf heeft reeds laten doorschemeren aanpassingen te overwegen. Een eerdere klacht in Groot-Brittanië is afgewezen, omdat de dienst nog niet commercieel beschikbaar is.
In een begeleidend schrijven bij de afwijzing, meldde de Britse autoriteit op dit terrein, dat de plannen niet tegen de Europese regelgeving leken in te druisen: "Zolang Google helder en transparant is, is er geen probleem. [...] Zolang [Google] de toestemming van gebruikers [maar] heeft." Precies op dat punt haakt Privacy International in. De "gemeenschappelijke" aard van e-mail zorgt ervoor dat het toestemmings-argument onbruikbaar is. Diegene die mailt naar iemand met een Gmail-account kan niet van tevoren zijn toestemming geven voor het eeuwig opslaan van diezelfde e-mail. Google zelf stelt actief op zoek te zijn naar user-feedback en dat naar alle bezwaren geluisterd zal worden.