Try going to your email account, not through your phone but on a PC because on your phone it sometimes doesnt give you all of the options, then go to your "My Contacts", and open up the settings. There should be an option to disable this feature of automatically adding email addresses.
I think it's adding them from my google mail. Anyway to fix this. I used the instruction you posted but I don't see that option in my gmail acct from my pc