Regardless, when the NAT table is full, it ought to expire the entries exactly as you said -- the connection with the smallest amount of time-out remaining ought to be removed so a new entry can take its place. It shouldn't flush the entire table. Unfortunately, I've seen the wrong behavior on many devices, not only D-Link, and I think part of the problem may be in memory allocation makes it hard to predict exactly when memory is actually going to be full.
Gamefuel is on its defaults as the ports used for torrents are not always known - majority of time the lockup has happened is when guests are over and are torrenting.
UDP entries, caused by DHT/Distributed Database, is usually one connection type that's easy for your friends to turn off. PEX works just as well and doesn't take any NAT slots.