I suspect that your router is not dropping TCP connections*, thus clogging up the NAT table. Do you have a way to lower TCP timeout? 


* Note: connections as in TCP connections, not the number of peers you have a connection to