Hi!
Just checked the site, the server gives a very weird response with dozens of different cookies, that should not be there, also there is a repetitive no-cache pragma printed all over the response header.
I don’t think it’s related to the search plugin, as it does not manipulate the response headers in any way. It migth not be a plugin related issue at all. I’m thinking of a lower level server-side cache like varnish or something similar, I honestly don’t know, it’s impossible to tell based on the response only.
What you can try, is to turn off the custom ajax handler, and use the WordPress default on the Compatibility Options submenu: http://i.imgur.com/0PWzHSc.png
I have seen similar issues with some security and cache plugins, which sometimes block ajax requests as false positives, causing no response. If that’s the case, then the suggestion above should help.