Thank you for your kind words, and te proper details!
The issue was a hidden tag filter, that was still active, but not visible. It restricted the results to certain tags only. Under the Frontend search settings -> Post Tags panel I disabled that filter, now it should be returning the correct matches.