Just a note on performance when doing distance searches:
Sorting X records by distance from the user requires computing the distance for every record, then sorting by that, then returning the number of records requested.
You're sorting by a dynamically generated field (e.g. there's no index to speed things up) so every record gets touched at least twice (once to calculate, once to sort). That's a lot of work to return the 5 closest stores. Paginated results may run that query several times (unless it's cached by MySQL or WP) to serve up results.
Depending on the number of records and number of searchers per hour/minute, you can quickly overload any DB server with these types of searches.
You can optimize a bit by excluding records that would never be viable options (e.g. use a geofence -- someone in CA is unlikely to be in the top results for someone searching in NY) to reduce the performance hit. Not sure if any of the plugins mentioned do that. I'd suspect not, as it requires assumptions that are different per implementation.
So, tread carefully to avoid bringing down your DB server (and with WP, your site).
_________________________
Nick Ciske
http://thoughtrefinery.com/
@nciske