Yes - this can be caused by three things. iCloud being messed up (and trying to sync your internet accounts) and corruption on the Mail settings and corruption in general in your user settings.
To troubleshoot this:
A. Write down your add/remove procedure and don't deviate from it. My guess is it should be:
- Quit Mail and make sure it doesn't launch when you log in
- Remove the account from system prefs
- Add the account in - optionally test something other than mail first like a bogus calendar entry to check the account and google servers.
- Test Mail by enabling the account and then finally launching Mail
B. Set up a brand new user account - with no iCloud and no Apple ID. Try adding the mail account there from System Preferences - Internet Accounts Preference Pane
If that doesn't work - your gmail is messed up or you need to reinstall the Mac from scratch (i.e. something is really wrong with the OS - this would be my last resort - make sure Gmail settings are clear at that point before backing up and wiping the Mac)
C. Sign out of iCloud on your Mac with your normal account.
Get a good backup before you delete content on the Mac. You will want to delete anything that's synced to iCloud to let the system clear out data that depends on iCloud. If you're paranoid, export data like Contacts and Calendar to a stand alone export/backup before you take this step. Then repeat the remove/add procedure.
D. Go to the logs. You'll need to run sysdiagnose Mail and then get into Console app and perhaps Log Connection Activity by opening the Mail Connection Doctor and checking that option.