Hi I'm having exactly the same issue as you.
What i'm doing right now is taking a backup of the database, enable debug mode in web.config (to avoid timeout exc) and running this code on an aspx file:
CMS.DocumentEngine.TreeProvider tree = new CMS.DocumentEngine.TreeProvider(CMS.CMSHelper.CMSContext.CurrentUser);
DataSet documents = tree.SelectNodes(CMS.CMSHelper.CMSContext.CurrentSiteName, "/%", "en-us", true, "CWB.NewsComment", "DocumentName like '%2rand%'", null,-1,false);
foreach (DataRow doc in documents.Tables[0].Rows)
{
CMS.DocumentEngine.TreeNode tn = tree.SelectSingleNode(Convert.ToInt32(doc["DocumentNodeID"]), "en-us");
tn.Delete();
}
This is slow as hell, but well, i'm guessing there is no other alternative.
I would be helpful to have some sort of procedure in the database to make such kind of things.