SimpleMap is an easy-to-use international store locator plugin that uses Google Maps to display information directly on your WordPress site.
Don't be too put off by negative reviews - it works reasonably well out of the box so I'm glad I tried it.
I can't speak for the support as I've not needed it, but documentation seems to be lacking. I'm loathe to criticise something that's free though, so give it a try.
For others looking to use this plugin, be aware that you can alter the display of the search form with shortcode attributes - it took a lot of digging around to find this, and doesn't seem to be documented on the WordPress.org site or the plugin's own website.
[simplemap] you can use something like
[simplemap search_form_cols=4 search_fields='labelbr_street||labelbr_city||labelbr_state||labelbr_zip||labeltd_distance||empty||empty||submit||empty||empty||empty']. This would change the number of columns in the search input table to 4, and then long parameter specifies which table cells to drop in the inputs.
There are other attributes you can change - just take a look at the defaults in \classes\simplemap.php around line 2318.
Thus far it works very well! It does exactly what it says it should be able to do. There is a lot of flexibility with the functionality and setting as well as the styling of the plugin.
I do however wish there was a way to include an image with the locations.