This truly does seem like an act of miscommunication on your behalf. Google is not in any way a fraudulent company, nor do they purposely mislead or 'scam' their users.
From my understanding, Google is under the impression that your problem is related to their Gmail service, which it is not.
Quite simply, you tried to add a domain name to your Google Webmaster account, but received an error as that domain had already been added and verified by another webmaster user well over a year ago.
If that is correct, then you will need to request for Google to change the ownership of your domain name, or to allow for you to verify that you are in fact the owner of the domain in question by uploading an HTML document to the website hosted at your domain. (although, there's a chance they'll request for you to change something from your domain registrar, as to confirm that the domain wasn't hijacked)
As for how this problem could have occurred? There's two possible reasons.
1. The website that you host at your domain was compromised, allowing the outside party to verify the ownership of the domain by uploading a document to your web server. (you said this was unlikely, though)
2. The domain name in question was previously registered by the other Webmaster user in a legal and legitimate way, but had later expired, allowing for you to register it yourself.
Since you've stated you had not been compromised, the domain expiry is the only other logical explanation here, albeit even that is fairly unlikely.
This problem can be resolved if you properly explain your situation to Google. Note that Gmail is not a part of the Webmaster Tools service, so please be sure to specifically specify Webmaster Tools when requesting for the domain to be re-verified.
Hope you get everything sorted out.