Hello,
I have worked with GPS data and geocoding services for many years.
I have used Google Maps, OSM, some local providers for geocoding (both forward and reverse). I have also built a cache of about 10 million points.
The Google Maps for Work license will give you 100 000 requests per day (still not enough for your requirements). One solution is to setup a server with OSM data and using that.
It also depends a lot on the region you are interested in.
Can you please share the sample file you mentioned? It does not appear to have been attached.
Best wishes,
Ionut