Hi Kari,
As far as I know, translating the taxonomies does the same as translating the posts in WMPL – it creates a separate taxonomy term for each translation. So basically the original and the translation are separate terms, not the same. The search requests them with the default get_terms(..) function, and that always returns the corresponding terms for the corresponding language, so it works with them.
Maybe this is best left untranslated, or perhaps the translation and the original term should be assigned to the posts as well.