У нас нет NAT под такой нагрузкой, но несколько замечаний общего плана всё-таки дам.
1. В ipfw операция поиска по таблице ДОРОГАЯ. Старайтесь по возможности делать таблицы поменьше и по таким правилам не прогонять пакеты, которые заведомо не предназначены для этих правил.
2. Количество инстансов ipfw nat лучше всего сделать равным количеству физических ядер системы, как и количество тредов драйвера сетевой карты - для уменьшения lock contention, что и приводит к нелинейному росту загрузки процессора за счет ненужного оверхеда.
3. Обновите систему до STABLE, в интелевских драйверах были нужные обновления.
4. Прочитайте главу в Handbook про DTRace: http://www.freebsd.org/doc/handbook/dtrace.html
Не пренебрегайте этим замечательным инструментом, он в неактивированном состоянии практически не сказывается на производительности системы. Прогоните профилирование хотя бы в течение пары минут в час наибольшей нагрузки, как написано в Handbook - узнаете, куда копать надо именно вам.
5. Почитайте Черникова: http://lists.freebsd.org/pipermail/freebsd-hackers/2012-July/039640.html