Thank you!
I managed to find the issue. A 3rd party script is contaminating the search settings form in the header with additional inputs, as you can see on this screenshot. This is not part of the plugin, this element is injected into the search form itself, and when the search is initiated it is sent to the back-end. It looks like it is for some sort of cookie validation or something similar.
That alone would not be an issue whatsoever, however after the data is sent to the back-end, when it reaches to ajax search pro, these options are completely wiped out, so malformed data is reaching the plugin, causing the issue.
I suspect this is caused by one of the plugin scripts – something to do with cookies/firewall or something similar. The element is injected, so I can’t trace it back to the origin, but based on the injector function name apbct_attach_event_handler__backend it seems to be Spam protection, AntiSpam, FireWall by CleanTalk. If you use a plugin by that name or anything similar, then it is very likely causing the problem.