Interesting. I saved all the search options again, as well as the WPML option. Checked the file editor as well, made a change on the search plugin files then reverted back to make sure it is consistent as well, it did not work. I have added a few modifications to one of the search plugin core files to forcefully fetch the language, and it works.
I guess that somehow circumvents the cache miss or something. Anyways, I think I can incorporate that change in the upcoming release as well, without causing any trouble. For now, just keep the search plugin files as they are, don’t reinstall the plugin if possible.
I will deal with this in the upcoming release, so you don’t have to worry about it. Hopefully it works now.