I think you omitted the "erroneous" part of that definition. From http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1570.pdf:
3.4.1
1 implementation-defined behavior
unspecified behavior where each implementation documents
how the choice is made
2 EXAMPLE An example of implementation-defined behavior is
the propagation of the high-order bit when a signed integer
is shifted right.
3.4.3
1 undefined behavior
behavior, upon use of a nonportable or erroneous program
construct or of erroneous data, for which this International
Standard imposes no requirements
2 NOTE Possible undefined behavior ranges from ignoring the
situation completely with unpredictable results, to behaving
during translation or program execution in a documented manner
characteristic of the environment (with or without the issuance
of a diagnostic message), to terminating a translation or
execution (with the issuance of a diagnostic message).
3 EXAMPLE An example of undefined behavior is the behavior on
integer overflow.
And later,
4. Conformance
2 If a ‘‘shall’’ or ‘‘shall not’’ requirement that appears outside of
a constraint or runtime constraint is violated, the behavior is
undefined. Undefined behavior is otherwise indicated in this
International Standard by the words ‘‘undefined behavior’’ or by
the omission of any explicit definition of behavior. There is no
difference in emphasis among these three; they all describe
‘‘behavior that is undefined’’.
...
5 A *strictly conforming* program shall use only those features of
the language and library specified in this International Standard.3)
It shall not produce output dependent on any unspecified, undefined,
or implementation-defined behavior, and shall not exceed any minimum
implementation limit.
Substitute "strictly conforming" where I said (colloquially) "well-formed". Footnote 3 basically says that a program can still be strictly conforming if it uses of conditional features has conditional guards.
All of that above tells me: "implementation-defined" and "undefined" are different concepts in the C standard, and programs with "undefined" behavior are erroneous - or, colloquially, illegal programs.
Oddly, I still agree with your final conclusion: gcc and other compilers are definitely allowed to do what they do; they are following the standard.