The title is misleading, they cannot use the gmail brand because it was previously owned by another company, so now they've to use Google Mail as their brand. No surprise. I can not call my company Coca-Cola. Can I?
Only a fair deal. It's however sneaky from Google that they tried to take cancel his trademark, even though his service existed 4 years before google entered the mail market.
Prior existence is only one of the tests for trademark validity, although I certainly can't claim any special knowledge of this case or German trademark law. It's fairly common in a dispute like this for both sides to make various arguments about the other sides claims. It's certainly not "sneaky".
How many German employees does Google have? It would be amusing to just close their German office and call it gmail again.
How would closing their German office solve anything?
Google says: "We can't provide service under the Gmail name in Germany"
I'm pretty sure German laws only apply if Google has an office there. If they closed their office, they could call the service whatever they wanted.
If they charge a German company to advertise on a German user's email account and they are trading a GMail then it could be a trademark infringement. It doesn't matter where they have offices and it doesn't matter that they don't have control of gmail.de
I'm going to make my own lemonade and sell it under the name Coca Cola around the globe (Except in the country where my company resides). Why didn't I think earlier of this?