I would poke around in the settings of my contacts app to see if the contacts listed there are filtered/limited in some way. Filtering may include/exclude gmail contacts, other mail contacts and (for phones) SIM contacts and more.
Above comments are based on my memory of behavior of gmail on pc where I don't expect autofill for anything other than what's in my contacts somewhere. But it may depend on the mail application, maybe some only require that you have received an email from the address as Funky suggests (in which case I presume the address is stored in some database other than contacts).
