I have tried to reconfigure the search and run a quick debugging through the search code.
Unfortunately the problem is with the server low memory limit. Sometimes the site responds in 2-3 seconds, but most of the time it runs out of memory and throws an error message.
Sometimes it does not even reach the search plugin through ajax, it stops with an error 500.
I have tried to increase the memory limit through php (you have 128M defined), but I couldn't do it. 128M ram is very very low for WordPress with a few plugins. You should increase it to at least 512M – or ask the server administrator to do it for you.Best,
If you like my products, don't forget to rate them on codecanyon :)