Tangent for bored hackers: you can torrent the entire OpenStreetMap dataset right now. It's only 23 GiB, in a simple format stored as protocol buffers.
You would still have to roll your own offline geocoder.
From my experience with OSM and Oracle's Spatial Geocoder, getting accurate driving directions can be a very 'interesting' process.
To a first approximation, the geocode data is embedded in the planet file (as address tags associated with some object or another).
But most consumers aren't using the data as organized in the planet file, they are generating extracts based on extent or whatever criteria, and usually processing the data into some data model that is better for the work they are doing.
See also http://www.datasciencetoolkit.org/, which has both a Google-style Geocoder and Street Address to Coordinates APIs. Uses OSM data, and ships as a downloadable VM with all data.
You can. For worldwide coverage you'd need at least 500GB disc space and 2-3 days of data crunching (assuming 32GB RAM, 8 cores, SSDs...) to build the Nominatim database. Photon is using Nominatim's database as input and will take another 2 days (if I remember correctly, met the author last year) to build.
(I work on OSM data professionally)
http://wiki.openstreetmap.org/wiki/Planet.osm#BitTorrent
http://wiki.openstreetmap.org/wiki/PBF (format documentation)
http://wiki.openstreetmap.org/wiki/Map_Features (common tag strings)
edit: This was my first render from this weekend, http://i.imgur.com/vD9d39W.png :D