This could be accomplished using the existing Internet DNS infrastructure with the LOC record type as described in RFC 1876.

For example, yahoo.com has a LOC record:
You could use this to return multiple LOC records, say for a chain of stores. Your GPS client could query for all LOC records for starbucks.com, and get back a list of the locations of each store, the client could then do distant calculations from it's current location and present the user with the closest Starbucks.

Of course, that would be a huge number of records, so it might make sense to localize using subdomains, such as "nh.us.starbucks.com" to only get the locations of stores in NH, USA.

The technology is out there, someone just needs to utilize it.