Hi,
Thank you very much for the details, it helped us a lot.
I did a full code review and debugged the queries – and found the issue. Luckily it was not a code issue, nor a server problem. The exact matching was enabled, which completely negates the index table. I have turned it off, it should be fine now: https://i.imgur.com/YjoZtQ2.png
Whenever that option is enabled along with the index table, a warning message is shown, but it may have been supressed via an ad-blocker or similar.
Anyways, it should be fine now 🙂