I think you misunderstand what the problem is.
Ajax is a technique to load data in the background without refreshing the page, which is what my plugin does once you click on the submit button. A request is send to the server, it returns store data and only that part of the html is replaced.
The same technique is used by other ( probably all ) store locator plugins out there, mine is no different.
So the problem is not caused by the way my plugin loads store data, or any others. It’s caused by your theme ( or any other theme ) using Ajax not just to load a small piece of data, but the entire page ( which as you notice can cause other issues ).
When that happens the code that is used to detect when the document is ready fails ( html page finished loading ), because it’s never “ready” since no normal reload ever occurred. Instead it just replaced all the content.
If you open the /js/wpsl-gmap.js you see at the top the document.ready code, that is never triggered on your page when you use the navigation. It just replaces the html so “ready” is never reached, which it does when you just F5.
I had one other user that had this problem, but he just disabled the Ajax navigation on the settings page in his theme.
I will let you know if I find a solution to this problem.