Hmmm, that’s going to make it a little difficult to troubleshoot.
Can you turn permalink back on and install the Rewrite Rules Inspector plugin. Paste the 404 search url into Rewrite Rules Inspector and send me a screen capture of the result.
Also, before a search is executed, view the page source and copy paste it into a test file.
Attached both the screen capture to a private reply. Hopefully they’ll help point me in some direction to give advise.