I made good experience with nominatim.
Try this (College Park in Toronto)
lat long lookup
address lookup
More examples can be found here examples.
It is in German but the examples are self declarative.
I guess the premium product is googles map API. Therefore I mentioned just something which might be an alternative.
The answer to this could be VERY broad in that it really does depend on what you want it to do. Generally, the way a complex geocoding system works is there are multiple layers that the geocode operation runs against, in a specified order. So, for example, many of them will look and try and match the input up with a point of interest by name, then it'll try and match against address points, then it'll try and interpolate an address by a road, and finally it may resort to using generic community name &/or zipcode matches. Furthermore, many of these will have some sort of threshold system set up for each layer, such as allowing a low match tolerance for POI matches because someone may have slightly mis-spelled something (matching Bob Mountain Range with Bob Mountains), but having higher tolerances for addresses because you don't want it to take you to West Main St instead of East Main St. So, when you type in an address to geocode, it will search these different layers, in order, looking for matches and will return the best match from the first layer that returns a sufficiently precise match to meet that layer's threshold.
Now, I say all that because reverse geocoding can work very similarly, if only in reverse. Instead of the user providing an address and it doing textual searches through attribute tables of layers and returning the geometry of matching features or interpolated geometries; you provide a location and it searches the geometries of various layers and returns the attributes or interpolated attribute of a nearby feature. However, a complex geocoder should be able to support complex reverse geocoding as well. Just as you can set tolerances for geocoding, you should be able to set layer specific thresholds for reverse geocoding. So, just for example, you provide an input XY location and it searches within, lets say, 0.75 mile for a matching POI. If no POI is returned, it looks within 0.5 miles for an address point. If no address point it searches within 1 mile for a road to interpolate an address from. If no road it searches within 10 miles for the closest zipcode or city center. Now, that is just an example, but hopefully it gives you some ideas in setting up your new system.
Hope it helps, let us know if you still have questions.
Best Answer
Looks like the Google reverse geocoding API will break it down for you, take a look at this result:
http://maps.googleapis.com/maps/api/geocode/xml?latlng=40.714224,-73.961452&sensor=false
If you switch out
xmlwithjson, you can get json instead. Another option could be the Nominatim service, which also returns either xml or json.