I had old auto-complete addresses popping up on my Gmail app on my phone, and different ones popping up on my computer, which was completely annoying. So this is what I did, with help from this thread and a lot of other googling. Full disclosure, I do NOT have a HTC one, but this was the most useful thread I found on the problem.
STEP ONE: Preventing future issues.
To prevent this from happening in the future, first I did what DLeo suggested.
On the computer, sign into your Goggle account. Open Gmail. Click the Gear icon to get to Settings, General Tab, scroll down to "Create contacts for auto-complete", Check "I'll add contacts myself".
Be sure to click Save at the bottom of this screen.
STEP TWO: Cleaning up bad contacts (still on the computer).
Go into Contacts on the computer. Go to More, then Other Contacts (this took me to the "old" contacts, where you have to again choose "Other Contacts"). Go through the list that appears and delete all the email addresses you don't want. Heck, while you're here, you could go through all your contacts and clean them up...but "other contacts" seems to be where Gmail stored the addresses of everyone I ever emailed.
STEP THREE: Log out, repeat steps 1 and 2 on the computer with other Gmail accounts you have. (I needed to log out and log back in before I could stop seeing the bad auto complete addresses on my computer.)
STEP FOUR: Clear Data and Cache - in ALL mail apps!
This is when I did many, many things on my phone. I removed my google accounts from my phone, re-added them. Cleared data and cache in the Gmail app. Cleared data and cache in the Contacts app (if you do this, make sure you have a backup first, somewhere). Filtered contacts in the Contacts app. Restarted phone. Synced contacts for Gmail. But every time I went into Gmail to test this, no matter which account I tried, I kept getting the list of auto-complete addresses that didn't seem to exist anywhere else.
It occurred to me that I also have a hotmail address on my phone, in the standard Email app. Just on a whim, I went into Apps - Email and also cleared data/cache. A bunch of the bad addresses showing up seemed to be ones I had only emailed through the Gmail app, but still..I was desperate. After re-adding the info for my hotmail account back again, all the bad addresses finally disappeared everywhere, including from the Gmail app!
(I went onto my hotmail account in the web browser on my computer and clicked on the menu to go to People. None of the bad email addresses showed up here, but I still cleaned up the whole contact list. Then I went back to outlook.com and went to settings, options, then Advanced Privacy Settings where I selected "only suggest people in my contact list" and hit save.)
Super annoying problem, but glad I found this thread which sent me down the right path. I'd already suspected that Google tracks and remembers everything about me, and I know it for sure now.