It's been at least forever, if not before that (probably goes back to the days of Open hat racks)....
I believe the document mentioned by the OP was issued around the same time the rules came in forbidding the use of under seat space for the storing of small children......