Although that model of router is not the champ of the Cisco line, I can't imagine any good reason

for it to act that way. Could it be that you may have "tinkered" it to death?

I would expect even a generic cheapo device to perform better.

Do you happen to have a smart net contract for it with Cisco? I would send it packing.

I would bet any additional tinkering would probably make it worse.

How much RAM does it have?
When you say tons of entries, what does that mean exactly?
When you say your connection lags, how so? How much?

What are you serving up to the outside?