Thank you for your insights, I hope that code helps.
It was working until the most recent release, because the wpml_permalink API call was actually used incorrectly, and it caused issues on other WPML installations. In your case it worked incorrectly, but that was the correct way (defaulted to the current site language, while the correct language was the original).
Those products do not exist in the database, so the plugin cannot find them, WPML just makes a way to access them via the other language URIs as well – but still, only a single product exists. If I understood correctly, you don’t actually have a translation made, and have an assigned language, the products are only in english. The search requests the result URL, which is the english version – but still, the other language versions will work, but those don’t actually exist (if the tranlsation does not exist).
The custom code I suggested should try requesting the permalinks by the current site language – even if the translation does not exist.