Regardless of what locales that have been defined for the taxonomy, the categorie translations only know about the language. Thus if locales of the form nl_NL are used then the category will have a language nl. However, when searching for translations matches are made with locales. Since the locales in this case are more than just the language it becomes impossible to match the locale to the translation. It is the plugin itself that explicitly loses this information when it creates a new category.