Thank you for the detailed description, it makes my work much easier.
So, I have looked at the issue, and I may have found the reason for the behavior as well, but unfortunately it's very likely not related to the search at all. Basically, the AD link get's randomly injected into the page to placed where I believe it is not supposed to, see this analysis: https://i.imgur.com/9A0URR1.png
It's very likely due to a minor programatical error within the ad script, or it can be something with the configuration as well. I'm not familiar with how it works, but I'm guessing that the ads are being placed to certain positions on the page by the script. A small error within the part where this position gets retrieved could very well explain this behavior.
Essentially the issue is caused by these link tags injected to the page, which surround some content elements (including the search bar), and when clicking on the search, you actually click on a link that contain the search, therefore you get redirected.
Unfortunatly I don't think I can do anything about this from the search plugins perspective. Let me know what they find, in case I need to do anything with the search plugin.Best,
If you like my products, don't forget to rate them on codecanyon :)