1) Actually, I think you'll find that the formats are "sorted" (within
groupings) by increasing # of characters: 1st example has no leading zero,
2nd example does. I've always found that to be pretty consistent. The list
isn't especially random.
2) While your " 4-Mar-01" and "04-Mar-01" would work for formats that
include text, 4-03-01 and 04-03-01 would raise the question "Which is the
day and which is the month?" (i.e., there is a reason one of the numbers in
the "type" samples is always greater than 12, and thus can't show leading
zeros in the example).
3) "The user finds out after he executes the formatting, not before." Huh?
There is a "sample" box in that dialog that shows exactly how the value in
the currently selected cell would appear with the currently selected format,
before the user exits the dialog and "executes" anything.

HTH,