Why is that even a question? Of course it's legal. It's in the terms of using their service in the first place. Nobody's forcing anybody to use Gmail, after all.
Maybe this is a difference between the US and Sweden, but at least around here, there are plenty of things that are illegal even if clearly stated in the terms of use and there is no compulsion involved. For example, it's illegal to sell yourself into slavery, even if you and your buyer both agree to it. A better example might be that it is illegal to sell ones vote in national elections.
(do not infer that _I_ think that scanning emails to show ads _should_ be illegal)
We have the same sort of law, of course. It's illegal to sell yourself into slavery, illegal to sell human parts even if they're yours, illegal to grow and sell marijuana to your neighbor (um, well, that one's changing).
So clearly there are contractual acts that are illegal. This one isn't, and I find it odd that people would expect it to be, especially given that people don't otherwise seem to care about privacy at all - as long as somebody in arguable authority says it's for their safety from Bad Guys.
> Nobody's forcing anybody to use Gmail, after all.
I think there are a couple of audiences who are; ( 1 ) employees of companies ( or students of institutions ) that have migrated to Gmail / GApps and ( 2 ) senders of e-mails who are unaware that one or more recipients are Gmail users.
For protecting the latter group, it is possible to configure most MTAs to hold or decline delivering to Gmail or any other arbitrary domain. For example, postfix has the 'smtpd_recipient_restrictions' directive.
What about Google Apps, which host domains that the user doesn't know belongs to google? Google can basically spy on anybody. Sort all emails to and from any email address and probably get a ton of stuff.
Then again, I suppose theoretically that's true of any large email provider. It just seems more egregious from Google since they are reading 3rd party emails to deliver ads...
(do not infer that _I_ think that scanning emails to show ads _should_ be illegal)