Building a store locator with google maps

You should be able to do this completely with custom post types. Most of the structured info can go in custom fields.

For the geographical info you can read “Optimizing a Proximity-based Store Location Search on a Shared Web Host?“, where I explained how to store the coordinates of the stores not only in the postmeta table but also in a separate indexed table to allow quick lookups. Another user of this site packaged this functionality in his Geo Data Store plugin, you can also take a look at that.