It's important to realize that CGI programs do not talk HTTP, they talk CGI.

Again, that's not always true. The specific secton of the CGI specifications that you're trying to cite is labeled Parsed Headers, which is a certain type of CGIs (although, they are the most prevalent type of CGIs these days, and many folks aren't aware of the alternatives). NPH CGIs are expected to return valid HTTP (see the section 'Script Naming Conventions' on that same page).

The point that I'm trying to make that these are not absolutes -- the HTTP/CGI/HTML specs are relatively lax, and there is plenty of leeway on implementation. (and I'm not trying to say this is a good thing, either -- although it made adoption easier, it has made it much more difficult to achieve consistent results across browser implementations)

In the recommendation made to fix the problem, the issue wasn't the lack of a Content-Type header, it was the lack of any header. So although adding a Content-Type header fixed the problem, it's important to realize that having added any header would have fixed the symptoms that were described. (assuming that was the only issue, which apparently it wasn't)

Any HTTP/1.1 message containing an entity-body SHOULD include a Content-Type header

As I said -- not required. As specified in RFC 2119:

3. SHOULD This word, or the adjective "RECOMMENDED", mean that there may exist valid reasons in particular circumstances to ignore a particular item, but the full implications must be understood and carefully weighed before choosing a different course.

If it were required, it would say MUST, REQUIRED or SHALL. Unfortunately, there are some older browsers which will look at the file's extension, and try to determine file type from that. (some would even prefer the extension over the Content-Type sent). Most servers running in parsed header mode will insert a Content-Type if there isn't one there, but many (Apache included) default to text/plain rather than text/html.