Okay, so what about this:
Students rank their course preferences in an order and submit it. For each course, free seats are first allocated to the students who ranked it as their first choice, then what is left to the students who ranked it as a second choice, and so on until the round n and there are less seats available than people who ranked the course as their nth choice: the remaining seats are allocated by a lot to them. (For a very popular course, they would have to start with the random selection right away on the round n=1).
However, instead of enrolling the lucky students right away, everyone gets notified about which classes they have been tentatively admitted, and they must confirm their attendance before they can take their seat. If they don't confirm in a timely manner, they lose the opportunity and the free seats are propagated to students left in the waiting list until someone accepts (again using random lot).
The one problem I can think of: the process (especially the propagation of rejected offers in the waiting list) may be too long-winded to be practical. So maybe skip the confirmation part: there's a set maximum number of courses you can take, M, and slots are filled until you're enrolled to maximum of M courses.
But in any case, if the overbooking is enough of a problem so that you are looking at methods like these, the real problem is that have too many students compared to the teaching resources. All other attempts can only mitigate the symptoms of the root cause.
So maybe staff should choose limit the amount of students eligible to take some very popular courses by an entrance exam, or imposing certain mandatory minimal GPA requirement in the prerequisite courses. This option should be especially considered if the attrition rate is high (there's a problem of students taking much-coveted seats in the class but who fail to show up or otherwise don't put in enough effort to pass). Usually that would have been done on the admission level already, though.