This covers two bugs around recentf-auto-cleanup being
deceptive/unintuitive.

Both bugs are present at 26.3 and on Emacs master as of
556cc727e5076d590f8286406e4f46cff3cee41e
at Sun, 16 Feb 2020 11:37:07 -0800

1. When setting recentf-auto-cleanup to a string, the timer does not
repeat.  It is only set once.  This is in contrast to midnight-mode,
which repeats its timer every day.  The documentation for
recentf-auto-cleanup does not make this clear, and I'm not even sure if
this was the intended behavior.

(defun recentf-auto-cleanup ()
  "Automatic cleanup of the recent list."
  (when (timerp recentf-auto-cleanup-timer)
    (cancel-timer recentf-auto-cleanup-timer))
  (when recentf-mode
    (setq recentf-auto-cleanup-timer
          (cond
           ;; snipped
           ((stringp recentf-auto-cleanup)
            (run-at-time
             recentf-auto-cleanup nil 'recentf-cleanup))))))

2. Due to the behavior of run-at-time, if the time string set was in the
past for today, recentf-cleanup runs immediately when recentf-mode is
turned on (e.g., at Emacs startup).  This makes it pointless to set it
to something like "3:00am" if I want recentf-cleanup to run at a time
when I'm likely not using Emacs and I have also set
recentf-max-saved-items to something large like 2000.  The docstring
does not make this obvious.  This is also how one would usually
customize midnight-mode.

2a. midnight-mode suffers from the same problem of using run-at-time,
but the default behavior of midnight-mode does not make it expensive.
But this means that adding recentf-cleanup to midnight-hook when using a large
recentf-max-saved-items will still be expensive at startup.

I have attached a number of patches:

1. Simply fix some awkward wording that is not directly related to this bug.
2. Document the current behavior.
3. Make recentf-auto-cleanup repeat for time strings.

The third patch can be skipped if deemed too aggressive, but I think
that's the more reasonable behavior to expect.

I have not fixed the problem of recentf-cleanup running immediately if
the time is in the past for today, since I'm not sure the best way to do
it.

In GNU Emacs 26.3 (build 1, x86_64-pc-linux-gnu, GTK+ Version 3.24.10)
 of 2019-08-29 built on juergen
Windowing system distributor 'The X.Org Foundation', version 11.0.12007000
System Description:	Arch Linux