Dear Stefan, 

I've tried now to follow as strictly as possible the instruction from
info node "(emacs) Sending Patches".

* Explanation of change: function `recentf-cleanup' can be very slow
  when the recentf-max-saved-items is significant, e.g. 60 items. This
  is due to this that duplicate items are removed with a iterative
  search (which means that cleanup is made in quadratic time). The
  change consists in using a search based on a hash table, so that the
  cleanup is in linear time. Function impacted are function
  `recentf-cleanup' and a new function `recentf-string-key' is created.

* patch made with diff -c is attached. 
   file [d:/msys/temp/recentf.el	Fri Sep 11 19:41:51 2009] is download
   from CVS, and file [recentf.el	Wed Sep  2 16:34:04 2009] is the
   modified one.