I'd like to preface this post with a disclaimer of sorts: I've only dropped by these forums every once in a while, and though I haven't seen this topic discussed anywhere else, I still suspect that I might have overlooked something related to it. If that is the case (or if this subject is something the developers would prefer that I not bring up here), then I apologize.
Sometimes I like to look through the resource files of older adventure games to see if I can find some material that wasn't included in the final product. I've found lots of unused animations, backgrounds and speech clips in the resource files of many of Sierra On-Line's games,* and to my surprise, I found some particularly interesting lines of dialogue in the resource files of "They Stole Max's Brain!" with the aid of Bgbennyboy's Telltale Speech Extractor.
(Note: To keep this list from being even more verbally tedious than it already is, I'll describe my findings as if the incarnation of the game that they appear in actually exists instead of saying things like, "Item X was originally in location Y" and "You originally had to solve Puzzle 3 in order to talk to Character 8".)
-Flint Paper actually shows up in the cultists' cavern in the beginning of the game instead of just appearing in a flashback.
-The "A Brief History of Bad Ideas in Transportation" exhibit is complete rather than merely being advertised as a coming attraction. There is narration about it on the audio tour, and there are descriptions of its displays, one of which is a boat called "The Screaming Narwhal" ("Although eminently seaworthy, The Screaming Narwhal, a pirate ship of unknown origin, was infamous for its inability to travel anywhere without a map.").
-There is a third puzzle that has to be solved to dissolve the alliance between Papierwaite and Skun-ka'pe. From what I've pieced together from the dialogue, in order to solve it, you need to take the Enigma deodorant from Papierwaite's office, have Sammun-mak shapeshift into the Toxicodendron palinus (the prehistoric poison ivy, which must have originally had a picture of it on its sign, along with all the other plants in the display), rub the deodorant on Sammun-mak, then put the deodorant back where it originally was. After Papierwaite goes to his office to freshen up and returns to the planetarium, he starts hopping around and yelping in pain. Skun-ka'pe thinks that Papierwaite is mocking him by comparing him to the "bug-picking simians" of Earth, and Papierwaite accuses Skun-ka'pe and his minions of causing the museum to become infested with fleas.
-The rebels don't just give you the brain screw -- they can only tell you that it is in one of the city's gift vaults. Norrington tells Max which vault this is (the one that appears in the final game, conveniently enough), and you not only have to find a way inside it, but also find a way to get Sam to pick up the screw (since Sam refuses to take anything from Sammun-mak without a very good reason, and Max is currently a bit lacking in the appendage department). When you ask Sal about the brain screw, he says that it was removed from the Museum of Mostly Natural History and placed in the vault by Sammun-mak himself.
-The sign-spinning minion is still advertising a pet store in the alternate reality, only the pet store is now selling crocodiles. You can have Sam enter the store, but he just walks right back out again, remarking that the crocodiles really don't like Max (a little like the Radio Yurt gag).
-Two of the accessories of power are considerably different: The Ornament of Fealty is the Ear Stud of Fealty, the Medallion of Tithing is the Ring of Tithing (or alternately, the Brass Ring of Generosity). I can see why they were changed, since an ear stud and a ring would be more difficult to see.
-There are a few more 2D images that Max can shapeshift into in the alternate reality. One is them is a picture of a corn dog (probably from one of the boxes outside Stinky's Diner). That's right: Max can change into a corn dog. As you might guess, this causes a lot of confusion for Sammun-mak when Max defiles the corn dog pyramid in this shape. There's also an image of an object that nobody can identify -- after Max destroys the corn dog pyramid as this object, Sammun-mak has to explain what it is (an ornate sandal-tightening device called a meshkant).
*I found a tiny graphic that looks a lot like Max's head in the resource files of Torin's Passage (which features a pair of skunks named Sam and Max).