Block protocols at the router: Some traffic--such as NetBIOS, SNMP and some ICMP types, including echo request, time request and subnet request--shouldn't traverse the border. Just drop it all at the router and be done with it. That way, even if a badly configured firewall crops up, the traffic won't leak out.
Implement tiered defenses: If you have one border router between your network and the world, what happens if it is compromised? Examine your traffic flows and design your network to restrict flows even if components fail.