Почему часть пакетов может не проходить маршрутизатор?

Куда копать? Что смотреть?

В первую очередь - firewall.

Более точно описать конфигурацию и проблему. И смотреть tcpdump'ом на интерфейсах.

выключи и включи сервера, обычно помогает.

Перезагрузку делал.
iptables -F делал

А где логи tcpdump'а и iptables?

>Сегодня утром проявился странный эффект: часть пакетов успешно проходят маршрутизатор (в направлении некоторых IP), часть (в направлении других машин - нет)

Для начала, лучше раскажите, как вы это определили? Смотрели tcpdump'ом? Ещё, кроме iptables можете покопать rp_filter.