I performed some quick additional tests with OpenBSD and vlan's just for the fun of it, although I belive these tests were more about OpenBSD's performance with lots of interfaces.
If you want a openbsd router/firewall with 4000 interfaces don't go for a low-end CPU =) http://www.layer17.net/openbsd-test-vlan-quick.html /Tony