I know it's inefficient, but perhaps it's possible that when someone selects to do a search, you export all or part of the DB to a text file and then perform the search (rather than performing it on the DB itself)?

It would at least be able to give you the functionality till you improve it.