I don't think it is mandatory that you have to select a course - you just don't click into that box and select one.
Unfortunately if another available course has been set to have course completion criteria it appears in this list.
There is no blank (or 'none') option within the 'courses available' drop-down list so the box cannot be left blank, i.e. a course is automatically chosen from the list even if I don't select a course.
Back to the drawing board...
Unfortunately there is an open bug for this http://tracker.moodle.org/browse/MDL-27114 which has yet to be completed (my fault).
In the meantime, the problem I believe you are having is that the form does not recognise a non-empty select box with nothing selected. Currently the only work around is to delete the course and create a new one.
Sorry for the bad news! I'll do my best to have another look at the patch soon.
not sure I completely understand which course to delete -- the one that is the prerequisite or the one that is dependent on it?
I created a new dummy course and made this the prerequisite course for all courses. Once I had assigned this to all the courses I then deleted the dummy course. I went back into each course and clicked save. The result of this is that 'completion dependencies' is not selected in any course.
It's a slightly clunky workaround but it does work. I'm looking forward to this bug being fixed.