I wrote
"Following examples show ..."
and my colleague revised it as
"The following examples show ..."
Why do we need "the" here even though the examples have not been mentioned before?
You need the definite article because they are still specific examples, even though you haven't mentioned them before. They're not just any examples, they're specifically the following examples, as opposed to the best examples or the examples of history or the examples I found in my sock drawer.
Whether something has been mentioned before is a good rule of thumb, but it is not the only rule for when you should use the definite article.
Reference: Using Articles
Because that rule you refer to does not apply about 70% of the time. Go and read anything in English and count the number of times a noun phrase is used for the first time with the.
A writer/speaker can use a definite noun phrase whenever he thinks the reader/listener can identify which thing(s) he is talking about.
The definite noun phrase the following examples contains enough information for the reader to identify which examples are being talked about. The examples that the definite noun phrase refers to are the ones that are about to be mentioned.
This type of reference is a cataphoric reference, which is a fancy way of saying that it refers to something that comes later in the text.
When a sentence begins with Following examples show the reader might think following is a gerund and therefore expect the sentence to be about the nature of following examples in general. The following examples show avoids this possibility.