I remember at a previous job someone cut the cost by only doing look-ups after the first three characters had been typed, and at another job someone getting an unexpected five figure bill (they had some explaining to do).
Esri has a free address auto-complete API, and unlike Google who suggests addresses that aren't legal, USPS deliverable addresses, you nearly always get real, valid addresses from Esri since they are pulling USPS's dataset (who is the only org that is legally required to getsl notified when a city or county renames a road, renumbers a block of buildings, etc).
