Hey Casper!
I ended up finding out what my problem was. The policy I had mentioned trying in my first post ended up being correct after all. It turned out that I had a rogue ejabberd policy in the system in addition to the policy I was testing, and the rogue policy had higher priority than the one provided by the RPM ☹
I must have installed this policy by hand some time in the past and forgotten to remove it. After removing it, I found that I just needed one more line on the policy to address this issue:
https://src.fedoraproject.org/rpms/ejabberd/c/d48066216cac7e2ec1626d65376313...
With this policy I am able to run ejabberd with STUN/TURN enabled and with the nis_enabled bool disabled.
There are updates for F33-36 in Bodhi now: