I have been working on the Tagalong premium plugin for a customer that requested per-category map icons. It is in VERY EARLY ALPHA stages at the moment. The new add-on will allow for custom map markers for each category of location. I am working on the search interface next and then on to the results below the map.
The screen shots are posted on the CharlestonSW website: http://www.charlestonsw.com/product/store-locator-plus-tagalong/
If you want to check out the screen shots and provide comments, feedback, or if you have questions about the new add-on please do so here at the WordPress forums so others can follow along.
I do NOT recommend purchasing quite yet and strongly recommend you DO NOT install on a production system if you grab the early alpha release.
Thanks for your interest and support!