Recently/frequently used items

Users are trained on our call-center software. The opening page is a list 200+ clients (buttons) from which they will pick a given client. We already have a search/filter - as soon as you start typing, the matches appear, then narrow down as you add more letters.

We want to add a Recent/Frequent section, so that their common clients are right there for them. I've read this question but want further clarification:

When showing a list of files, is there a preference between 'Recently Used' and 'Frequently Used'?

We are storing this using local storage.

I had started down the down of frequently used, but my boss pointed out that I have to store every client, and each one has to have a counter to keep track of frequency. His suggestion is to make it just like a cache - last-used item gets moved to top. (it's moved, not just added, therefore it never appears twice).

Need some guidance as to which is better for our purposes, and why.