I'm looking for a web service providing a full address based on coordinates (and reverse).
I'm ready to pay for that service.
I don't want to use Google's API.
Via Michelin (best for Europe)
Mapquest Open API (based on OpenStreeMap data) http://developer.mapquest.com/web/products/dev-services/geocoding-ws
Microsoft Geocoding http://msdn.microsoft.com/en-us/library/cc966793.aspx
I would highly recommend deCarta. We powered google maps, yahoo maps and a ton of other people. We just announced new pricing. We expose our geocoding (and reverse geocoding) through many different apis. We also have worldwide coverage.
We actually have other emergency systems running on our platform.
Note that deCarta was acquired by Uber]1 and their API is no longer available.
Disclaimer: I work for deCarta.
I suggest you try out Geocode.Farm (https://geocode.farm). You can always just past the address into the address bar the same as you would put it into a form and it will display in XML the output, but it is human readable:
Maybe this will work for you.
You can try PickPoint. That's a pretty expeditious service providing geocoding as well as reverse geocoding by attractive price.
You can even choose Free plan if the number of requests is below 2500 per day.
Posting a new answer here as this ranks highly on Google on the topic of Geocoder result licensing.
Here's what I understand to be true for the non-enterprise version of Google Maps / Google Places:
Place IDs are exempt from the caching restrictions stated in Section 10.5.d of the Google Maps APIs Terms of Service. You can therefore store place ID values indefinitely.
Based on my own recollection, Google Maps TOS has improved quite a bit, and they do clarify what you can and cannot do a little better now.
I was also looking for international geocoding and checked out decarta and viamichelin. I couldn't make heads or tails of the viamichelin site so I moved on to decarta. I downloaded their api and was geocoding addy's in Denmark in no time. Their prices are the best I've found on the web. I called them for some more information and the CEO of the company called back was extremely helpful.
Go with DeCarta - first 1,000,000 geocodes are free, $2.80/1000 after that.
For Europe try Geocode.XYZ
It is free. (based on openstreetmap and openaddresses.io ) Does Geocoding (forward and reverse) batch geocoding and geoparsing from text for over 50 European countries.