What kind of architecture is the site currently running on? Apache or IIS; PHP, ASP, Java, etc. If the search function has to integrate with the current site it is often a good idea to choose something from the same architecture family.
I use the Google Custom Search Engine on my Chinese websites. It had the best search results of any of the packages I looked at. Operation doesn't seem to be affected by the recent Google troubles in China.
sorry i don't have more to offer. i was peripherally involved a few years ago with a multilanguage site that used KinoSearch, which is based on Lucene, and i believe that was due to the capability to handle chinese language search.