Thank you, Tom!
We discovered this problem when releasing the auto enrolment plugin in May this year.

We searched for the cause (as you can read higher in this discussion) and the 'in some cases' are courses that were migrated from Moodle. Those courses had a different completionstartonenrol value than courses created directly in Totara.
We manually changed the completionstartonenrol field in the database to solve the problem.

Glad to hear Totara is fixing bugs for this plugin!