From the Info page "(cl) Organization" in Emacs 25.1.91:
Since the old ‘cl.el’ does not use a clean namespace, Emacs has a policy that packages distributed with Emacs must not load ‘cl’ at run time. (It is ok for them to load ‘cl’ at compile time, with ‘eval-when-compile’, and use the macros it provides.) There is no such restriction on the use of ‘cl-lib’. New code should use ‘cl-lib’ rather than ‘cl’.
MH-E uses cl but doesn't always avoid loading cl at runtime (see bug#25552 on debbugs.gnu.org). If we move to cl-lib, we could avoid this sort of bug and probably simplify the code.
See also #482.
In debbugs #25552, Glenn Morris noted that cl-lib is available from elpa.gnu.org for Emacs older than 24.3.
This was fixed by
and will appear in Emacs 27.1.