Ah, this question. First, let me say that I work for an address validation company, SmartyStreets, but I will try to be objective.
US Geocode data generally comes from two basic sources, FREE and EXPENSIVE. Let's go there for a little bit.
Free geocode data comes from the US Census Bureau. Some will tell you that it comes from USGS or even from the USPS, but the root source is the US Census Bureau. They have a somewhat comprehensive dataset of street segment coordinates, called TIGER data. The TIGER data is freely available for download (though it takes A LOT of manipulation to make it usable). The USPS has attempted to tie into the TIGER data and map it to ZIP Codes (which are NOT geo-political boundaries but instead USPS delivery areas based). There are many different services that utilize this TIGER data as their source for geo-coordinates. They use different algorithms to determine the position of an address along a street segment and then interpolate the geocode based on that algorithm. Because of the lower data cost and the licensing costs of the source data (free) many services will allow clients to store the geocode data that is part of the output data. SmartyStreets is one of those that believes that you can do what you like with the data.
Not free geocode data comes from a number of expensive source. These sources generally compile their own data, though they also augment that data with licensed data from other sources as well. You have sources such as googlemaps, nokia, navteq, bing maps, yahoo, mapquest... (Yes, I know, some of these are owned by the others.) Their data is much more expensive to acquire and their license generally prohibits clients from storing the response data.
So, you have free source data and expensive source data. Typically that cost is passed on in the form of more restrictive licensing. Hope that helps.
Here's a short list of providers that does allow for storing of the output data (certainly there are more):
geocod.io
smartystreets.com
yaddress.net
By the way, I'm the one that made the table that was referred to in the original post. I work with address data all day long at SmartyStreets.
--update--
@zsero Actually, I believe that data similar to that available from the US Census Bureau is available from a number of countries. Australia, for example, so I have heard. However, it's not necessarily the country that the data comes from but instead the level of accuracy. The US Census Bureau data, for example, provides pretty accurate geo-coordinates for street segments, but not for addresses. Address interpolation from that street segment (start or end point of the street) along the shapefile that designates the street shape is what allows "guessing" of where the address might be along the street. That's pretty good for statistical analysis. However for something like precision skydiving or a surgical missile strike, that wouldn't be good enough. You would want rooftop level geocode data. Typically THAT is the difference between the free and the expensive data.
