Hello @pixelshrink,
You can create something similar to what you described using 2 separate forms. One form will display only a map showing all the locations and the other form that will display the search form and search results.
Having it that way, the map will always show all the locations regardless of what is shown in the results.
Another option based on the setup above is to have the map of the second form shown only when the form is submitted. So on the initial page load, the map of the first form will display all the locations, and below there will be the second form that shows the paginated results but its map is hidden. Then, once the form is submitted, the map of the second form will be visible showing only the locations from the list of results. However, with this setup, the map from the first form will be still visible as well. So you will need to find a way to dynamically hide the map from the first form when the form is submitted ( probably using a custom JavaScript function ).
The above can be done using the different settings of GEO my WP’s forms. Anything else would most likely require custom coding.
I hope this helps.
Let me know if you have additional questions.