Random cursors behave poorly in workloads that have many deletions.  This ticket points out some of the anomalies and some potential fixes and/or improvements.  Part of of random iteration code includes code that selects a random leaf page.  As eviction uses this same random leaf selection, some improvements here may help with eviction for these workloads.

These workloads may not be uncommon at all.  Consider a collection that contains orders being processed.  An order comes in, a new order is created.  When the order is fulfilled, it is removed from this collection, maybe moved to a different collection of past orders.  If the key is always advancing, then over time get a tree with lots of pages that have no entries, or few entries.

In the comments will be a program that does a simple simulation of this situation and the surprising results of testing random cursors on this.

It's possible that multiple smaller tickets will spin off of this investigation.