There is really only one red herring in the game:
Spoiler:In the Village of Lost Children there is a building that actually HAS A RED HERRING PAINTED ON THE ROOF! When Max wanders into it, he says something like, "Hmmm... I would have bet there was something important in here." hahahahahahahaha