Do they have visibility to the catalog the course is in? Self-enrollment has to be enabled and there has to be an enrollment link (makes sense you have this part). But I found that you can enable the link without enabling self-enrollment. Then the link won’t work.

Yes they have visibility to the catalog, which is why this is throwing me for a loop.  My best advice to give so far is to “turn it off and then back on” …. I’ve noticed that even as a super-admin I sometimes get a 403 error and when I log out and back in it’s magically fixed.  One theory I have is that permission to enroll in external links “times out” after being logged in to the system for a while, even though everything looks to be working normally while in the system.  

If it helps diagnose, I set up permissions through auto-assignment into groups based on custom fields.  For this one specifically, a manager who is in the manager group, and by default is assigned the manager catalog, is getting a 403 error when clicking on the enrollment link to a specific manager course.  Other managers with the same permissions auto-assigned are registering without any issue.  

You can extend the login time in the advance settings. Also if you recently impersonated someone and you have that “tab” still logged in as that other user you will get a 403 going to something that user can’t see.

Have you pulled a course report and looked at the enrollment settings and links for the courses that are causing problems?