Thanks for the details. It took me a while to find the problem, and I'm afraid I can't fix it because it does not seem to be related to the search.
I will try to explain in as much details as I can:
There is a database error regarding the faulty terms. It's not visible on the back-end, only with a closer inspection. Let me try to explain with the term “Quito”. There is an english version with an ID of 1511, which should be the one that's returned within the results. However the term with ID 1513 is returned, which should be the spanish version, but it's not. I queried the database and the 1513 is marked with the language code “en”, which is english. More interestingly, the original english (id 1511) does not have a language code. To further prove the problem, if you for example go to the editor to edit the spanish translation of the “Quito” tag (id 1513), and the source terms is the same as the translation! So term 1513 is english, displayed as spanish, and it is it's own translation because of this error.
Demonstrated on a screenshot: https://i.imgur.com/IgCQh0o.png
I'm not sure what to do here. Perhaps deleting the Quito and all the fauty tags and re-creating.
Or maybe ask the WPML support first, to make sure I'm not mistaking anything, they surely know better than me.
If you like my products, don't forget to rate them on codecanyon :)