Further to the above the developer of the Ajax Search Pro plugin has come back with this analysis of the problem:
Basically, the AD link get’s randomly injected into the page to placed where I believe it is not supposed to, see this analysis:
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.
I was going to pay for the Pro version of AdRotate but the search function is integral to my site so if if this can’t be fixed I will unfortunately have to look for an alternative.