Aparently we missed a setting.
Changing at site administration level will only work on new courses. If you configure it at site level and then apply it to an existing course, it doesn't carry through your settings. That is a tad annoying, but at least I know what to look for now.
You actually have to go into the course settings > users > enrollment methods > self enrolment (student) and fix the setting there as well.
Off to create a brand new course and see what it does.
Thanks to Petr Škoda for that information.