Lot of pain to get Skype working properly after I switched from an increasingly complex ipfw firewall to a pf based one. Skype consistently gave me "UDP status: local: BAD". I believe that happens when Skype tries to use peers for udp traffic, instead of talking to the caller directly.

The solution was to use static ports for nat. My default rule in pf.conf was this:

nat on egress from any to any -> (egress) round-robin sticky-address

It is now:

nat on egress from 192.168.1.10 port 12345 to any -> (egress) static-port
nat on egress from any to any -> (egress) round-robin sticky-address

Skype now has UDP status local good, finally sigh.