I have something very much like this, a trivial addition to find-file. Typing C-u C-x C-f shows the recently edited filenames (with paths), and vertico + orderless makes it a joy to instantly pick the specific recent file. I get the same UI with regular find-file (C-x C-f), so the two bindings live harmoniously in my brain and fingers.
Before switching to vertico/orderless, I used ivy with essentially the same machinery. That worked great too.