I haven't been in contact with TAC, however, I tried enabling the extra logging as explained here: https://support.checkpoint.com/results/sk/sk113479
When doing that and then telnetting to an ip on 443 that gives me the "CpNotEnoughDataForRuleMatch" I get this expanded explanation:

I'm not sure I fully understand what it means, even after reading the explanation in the aforementioned SK.
Then I tried disabling rule 153 it mentions as a first possible rule match, but then it just says the next rule (154) is the first possible rule match. What those rules have in common, though, is that the source is a Network Group that consist of various hosts, networks and other network groups.
So to try to figure out if that particular group was the culprit, I created a new rule above the first instance where that group was used as source now with a single host as source and that particular ip (the one that otherwise fails with "CpNotEnoughDataForRuleMatch") as destination and action as Accept - and now it works, no error or anything!
It seems as that Network Group is what is causing this issue, but I can't figure out why. Do any of you have an idea as to why that could be the case? It is a group that are being used in many rules and generally it doesn't seem to cause any issues.
Looking forward to your ideas! 🙂