I managed to resolve my above issue and for anyone ending up with the same question:
My issue was caused because of a colleague who added a floating rule, rejecting traffic coming form another alias with logging disabled on that rule. Unfortunately that alias contained a different FQDN that resolved to the same IP of the removed FQDN.
What is the important lesson here:
Apparently the PF box handles floating rules AFTER interface rules. And since logging of that floating rule was disabled, the firewall log logged the allowed traffic from the interface rule, but blocked the traffic afterwards based on the floating rule with no logging! You end up seeing an allow in your log, but it is blocked in the end!
This must be a culprit some else will face one day or another :)