Which plugins are you using to change map markers and set icons? Tagalong for icons and markers, I’m assuming, but are changing markers anywhere else?
If you can provide the URL to your site and some specific search terms we can look at the JSON data coming back from the search results and see what is coming out of the database for marker info and go from there.
Tagalong markers are sorted by rank , then alphabetically. Only the FIRST map marker in the assigned category list is used on the map so you may want to check that.