I tried to determine the cause with different configurations but no success yet. I would like to run a line-to-line debugging on the search files, can you provide temporary ftp access for that?
500 error usually happens when a php script stops with a fatal error at some point. In this case I'm suspecting that the template is either using a function with the exact name as the search plugin, or restricting access to certain ajax hooks or something similar.
If you like my products, don't forget to rate them on codecanyon :)