Of all the places I saw on holiday, the most exciting was Milford Sound.
Why is it not?
Of all the places I saw on a holiday, the most exciting was Milford Sound.
I can count the holiday, so why is 'a' not required in this sentence?
Perhaps you should supplement your school rule (article + countable noun) by saying there are cases that don't agree with this rule. In very frequently used expression the article can be dropped as in to be on holiday or to be on business.
"On holiday" or "on vacation" is the expression used to denote a period of time away from work and school or away from home enjoying yourself. No article is used.