I have lately been doing some research for alternative geocoderes to Google, Yahoo and Bings geocoders, as they do not allow storing the received data (we need to receive geocoordinates in a mobile app, to minimize the time and data spend). The addresses are in Denmark, so two of the three alternatives I found only support Danish addresses:

• Nominatim — May not have complete data, but so far i have not encountered any addresses not supported. It takes about 3-13 seconds per request. It is the only geocoder of the three, that supports addresses outside Denmark. It is part of the OpenStreetMap project.
• Adressewebservices — Is a SOAP webservice that is created by the Danish Enterprise and Construction Authority, it is, however, the slowest of the three (about a minute per request).
• Vis Stedet — This service is developed by the Danish Ministry of the Environment. It is the fastest of the three geocoder. However, I am not quite sure about the terms of use, you may need a login to Kortforsyningen, even though it seems to be possible to use the geocoder without.

Some of these seems pretty slow, and user can not be expected to wait a whole minute for a geocoder to do its job, it therefore might be an advantage to use a cron-job or equivalent for this tasks, and collect the coordinates ones a day, or perhaps use the cron job in combination with the Nominatim service, which may be reasonably fast, and, if no result found, use the cron job find alternative coordinates later.