Errors within the 500 range (500, 504, 505) indicate server side issues. The plugin tries to make a request to the server, but it either does not respond or it fails.
If you want, I can take a closer look. Can you please add temporary FTP and back-end access? I will try to debug through the search process, maybe I can find something.
I’m creating a duplicate site to give you. Also, I noticed that this happens on the general search bar. I have around 75 search forms through out the website and the ones that are only focused on specific categories, let’s say definitions, the search bar works pretty fast. However, in the main one which search for around 5000 posts. It gives 504.