A powerful search tool can boost your site's usability. The built-in search in WordPress doesn't really give that. Fortunately, there's Relevanssi.
Basic WordPress search lists results according to date. Recent posts come first and older ones follow. If the best result is an older post, it will be buried under more recent entries.
Besides an accurate search algorithm, Relevanssi also presents search results much nicer. You can set custom excerpts that show the part of the post that matches to the query, with the search terms highlighted.
As of version 2.7.2, Relevanssi is fully compatible with WPML. Mikko, the author, added a small piece of code that checks if WPML is enabled. If so, it filters the search results according to the current language.
When you search from an English page, the search results will be in English. From a Spanish page, the search results will be in Spanish.