Hi Sam, some comments after (finally!) reviewing the code:
1) The "userscompletion" setting only determines if the user related information must be included in backup and restore. Just that. So, all the rules/criteria/whatever must be included in backup and restore without depending of the setting. So I would take out that condition from the backup/restore tasks. And, instead, use that setting within the backup/restore steps to decide about to backup/restore the tables having user-related information.
2) In the other side, there is one $CFG setting that should be used to completely disable restoring of ANY course completion information. It is $CFG->enablecompletion. You should check for it in the execute_condition() method of restore_course_completion_structure_step. See, for example, how we are handling restore_userscompletion_structure_step observing that exact setting.
3) Also, I consider that the course completion is something really similar to the gradebook information, meaning that we only can include modules infomation (criteria) if we know that ALL the activities are being included in backup. And the same happens in restore: We only can restore course information criteria if all the activities are being restored. Else, it can fail horrible (non existing mappings => orphan records...). I'd suggest you to take a look to the execute_condition() of the backup_gradebook_structure_step and restore_gradebook_step classes, they achieve exactly that (detecting that all the activities have been included).
4) About criteria information related to one module, you can safely get mappings for the 'course_module' itemname. But obviously, that only can be done after all the modules have been restored, so I guess you'll need to move the restore_course_completion_structure_step() from the course task to the final task (once more, like the gradebook). All the mappings are only available there.
Hope it helps. Finally.. note that I haven't tested it at all, so I rely on you about all the structures being complete and so on. Great work, thanks!