I noticed this curious “rule” mentioned back then when the South Park movie was titled “All Hell Breaks Loose” (1999)
But then I do remember “Jason goes to hell: The Final Friday” (1993) [no it was not the final movie…], “Hells angels”, “Hellboy” (2004) , Hellboy II: The Golden Army (2008) “Hell Fighter” and others.
So, does that rule exist? Or it is/was just a whim of the MPAA?
According to the IMDB, the MPAA has said that the title South Park: All Hell Breaks Loose" was never submitted to them, and they never denied the use of the word in the title. The many examples given in the OP would seem to back that up.
It sounds like Parker and Stone were making a joke.
Thanks RealityChuck, so that funny bit about the title of South Park was just a creation of Parker and Stone.
Man, you guys. “You lied to me?”
Well, the story of the South Park movie and the MPAA is a long and varied one. I don’t doubt that that title was never officially submitted, but they went back & forth with so many content challenges most probably weren’t ‘official’. If you read accounts of their ratings battle they’re really funny.
After initially getting an X rating several times Jack Valenti quickly caught on that Parker & Stone were specifically targeting and baiting the MPAA with their ‘changes’ (the movie rating system is a major plot point of the Terrence & Philip film within the film). I remember reading P&S describing a screening with Valenti about the scene with Winona Ryder and the ping pong balls and them having to point out, “Look, see! She wasn’t really shooting them out of her vagina! It was just a joke!”. Needless to say Valenti was not really amused*!* 
In reference to Parker & Stone and the movie’s eventual R-rating Valenti said that he felt that, “Those hairballs got away with more than they ever wanted!” and P&S didn’t exactly disagree*!*
Hell in the Pacific…1968 Lee Marvin and Toshiro Mifune rated G even though Lee Marvin pees on nhim.
Because it’s this board, I’ll point out that there is no more X rating. They changed it to NC-17 to deal with the fact that the X rating couldn’t be trademarked, leading to a lot of imitators.
Actually, the X could have been trademarked, but the MPAA decided not to. This was so that they didn’t have to make decisions on obvious porn films (or have their name involved). Porn producers could put on the X rating without them.