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.
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*!*
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.