Включить syn cookies, для начала:
sysctl net.ipv4.tcp_syncookies=1
Постойте, постойте...
512 соединений в состоянии SYN_RECV - для Вас это флуд?
Что у Вас за сервер такой?
Upd.: Посмотрите в dmesg - у Вас conntrack table не переполняется, случайно?
Обычно большое количество соединений (когда это действительно большое количество соединений, 65K и выше) забивает conntrack table - и вот тогда начинаются симптомы, похожие на описанные Вами. Либо я не понял фразы "сервер по сети начинает отвечать".