That doesn't really help since my problem is with PF (ipfilter works 
perfectly, as much as it does work at least)

PF under FreeBSD 5 works perfectly too.  Really strange.

I think I'll hold off NetBSD as an internet gateway for now. I'm still 
interested in possible solutions to the problem but I might not be able 
to try solutions.