By the way, we ran a query like this:

select cmc.* from mdl_course_modules_completion cmc join mdl_course_modules cm on cmc.coursemoduleid=cm.id where cmc.userid not in (select cc.userid from mdl_course_completions cc where userid=cmc.userid and course=cm.course

And we found that there is a pattern among all the records - a lot of the users has a deleted account. Maybe this is related to what you were talking about, that somehow the mdl_course_modules_completion table was not correctly cleaned up??