It might not happen only once in a while. Consider the following pattern in which a Fetch() does a Get and then an Insert on cach-miss:

   Fetch("1"); Fetch("1"); Fetch("2"); Fetch("2"); Fetch("3"); Fetch("3"); ...

This will result in your queue being 100% filled with items that are marked as hit because of the second Fetch for each key. After the queue is full each first Fetch will result in an eviction (new key to insert) which has to walk the whole queue because the only item marked not-hit is at the head of the queue due to being lazy promoted.

My O(n*m) reply was because your O(m) was considering a whole run over multiple requests and my O(n) was only considering one request. So if I were to also talk about multiple requests then your eviction algorithm needs to look at O(n*m) items for evictions in the example pattern I presented. O(n) per request for m requests.

A malicious actor could abuse this fact to cause a DoS.

No you can't just bound the number of objects it checks because that would result in a flurry of cache misses as it would mean you have to fail the insert.