More aggressively cleaning out our cache...

Be it hash table or AVL tree, we more aggressively pull out remote
entries to keep the size smaller.  Shrinks the size but at the cost of
a little more computation.