The London-based civil liberties group has approached regulators in France, Germany, the Netherlands, Greece, Italy, Spain, Czech Republic, Belgium, Denmark, Sweden, Ireland, Portugal, Poland, Austria, Australia and Canada, as well as the European Commission and the EU Commissioners' internal Article 29 Data Protection Working Group.
The group complains that Gmail, which is currently in beta testing, will electronically scan the subject headers and contents of all the private e-mails to generate targeted ads relevant to the e-mail content.
Google's site gives an example of how these ads would appear: in an e-mail thread among friends discussing a forthcoming concert, Google's service automatically detects some key words and, in a panel next to the e-mail content, displays sponsored ads for ticket retailers.
But Privacy International considers the scanning a breach of Europe's data protection laws, albeit the scanning is clearly explained in its terms of use.
The group had already attempted to get pre-emptive action from the UK's Information Commissioner, but without success.
A spokeswoman for the Information Commissioner's Office told Silicon.com:
"As long as it's transparent to people when they sign up that Google is monitoring their e-mail usage and passing that information on for marketing purposes, then they probably wouldn't be breaking any legislation. Until Gmail's up and running, though, we can't be certain."
In its new complaint, Privacy International says it is "the scale and functionality of the Gmail service that poses a heightened level of threat to the rights of individuals and to the security and privacy of communications."