Thanks for these incredible pointers guys! I've been experiencing MANY problems with this in the past months. Never was able to figure it out. It actually only occurred for all IPv6 traffic between two VLANs on my network being connected via pfSense. Since IPv6 traffic is prioritized over IPv4 traffic, when connecting using DNS or NETBIOS names instead of an explicit IPv4 address, it would always cause trouble. It wasn't just one protocol, it was with every protocol and every type of traffic (i.e. RDP, filesharing over NETBIOS, streaming audo, SSH sessions). Very irritating. Strange that it didn't occur with IPv4 traffic though. Switching the setting at System -> Advanced -> Firewall/NAT -> Firewall Optimization Options to conservative solved it all. And increased memory usage? Its still at 5% of the 4GB of RAM the machine is equipped with, just like it was before :)
Thanks!!