Making spells and abilities tie in to fluff more, like 3e rather than 4e, can add to mystery: instead of being a bundle of stats and scores, monsters react differently depending on what kind of power you use on them, like a mud to stone spell slowing a clay golem. This makes the game run on sense over numbers, makes monsters more unique, and rewards players for using their minds and figuring out what might do something useful to their foe.
Knowledge checks can have increased DCs, so that the expectation is that you have a fair chance of learning the basics (name, where it lives, who it eats) of a monster of an appropriate CR, with learning more details (hints at its weaknesses) for monsters with a CR 5-10 less than you, and "reading the MM entry" for monsters with a CR more than 10 below your level. DM rolls secretly, and if you fail by 5 or more, false information. Fail by 10 or more, dangerously false information. Common monsters would have slightly lower DCs, and rarer and unique monsters would have higher ones, to the point that any roll would only reveal the basics of a never-before-seen creature.