To implement on-the-fly MRU, it's simple:

• if A!=S then B <= A (and enable update) (else B)
• S goes to A.

That's it.

This takes precedence over the rest so adds a layer of MUX and some latency...

.

preliminary interactive playground here.

.

The added MUX layer is quite OK for the A output:

A <= S when MRU='1'
  else B when A=S
     else A;

Easy !

If MRU='1' then
  if A=S then
    B <= A;
  else
    B <= B;
  end if
else
  if ... then
    B <= newB;
  else
    B <= B;
  end if;
end if;

This "folding" else is not obvious to redesign. Ideally only a pair of MUX2 should exist.
And let's not forget the WB output.

Here is another temporary version.

.....

But I have finally found a trick by swapping the MUX, giving more time for the decoding logic and reducing redundancies. The current version is there:

The logic depth is about 5 gates and it supports both LRU and MRU modes. The approximate number of CMOS gates is 30, though going down to NOR/NAND logic could bring some enhancements, by sharing inverters for example.

Can I consider the case closed ?

I don't think so because I'll have to transcribe it to VHDL and then stress-test it with simulated worloads.

That will come later :-P