Use a Cisco DSL router (Score 1)

I've had the same problem with many simple routers. When you run P2P software inside you'll get lots of connections from outside, each entry requires a NAT table entry which expires slowly. I invested in a small Cisco DSL router which allows me to set the max. size and the expiry time of nat entries. Problem solved. Without the limit on the tables the Cisco would report the overflow after about one day.