It seems that there's a bug with some pages that have been deleted and restaured after that, but without any more modification. For example, on the French wiki, I get the error when trying to edit fr:Charbonnage. The page exists, its last version was one 2010-03-11 at 12:37:19, but it was deleted and recreated later this day (at 17:45).
Request made: http://fr.wikipedia.org/w/api.php?summary=[[:fr:Utilisateur:NicoV/Wikipedia Cleaner/Documentation|WikiCleaner]] 0.99 - Correction des [[Projet:Liens vers les pages d'homonymie|liens vers les pages d'homonymie]]&title=Charbonnage&text=[[Image:Drilling of blastholes with air drill.png||thumb|upright 1.5]]...&basetimestamp=2010-03-11T12:37:19Z&token=xxxxxx+\&minor=&bot=&action=edit&format=xml
Error reported: pagedeleted - The page has been deleted since you fetched its timestamp