I've been thinking about this question since about the time 3rd ed came out, and still haven't come up with an answer.
I think that normal monsters should be recognised using a wilderness lore role., while magical creatures with a knowledge Arcana role.
Undead would probably be best with a Knowledge undead, but I think that knowledge religion could cover ex-planar creatures.
There are plenty of other skills in WotC sources (eg Knowledge The Planes), and those from other sources, but I don't like skill creep (increasing the number of skills that a player can choose from, while their skill points available stay the same).
I miss the Frequency of monsters from earlier versions, but I realise that should be world specific (but MM/MMII/FF could list the World of Greyhawk frequencies). I think this stat would be useful in determining knowledge of monsters.
But I don't think it should definately become harder to recognise just because a monster is more or less frequent. For instance, I think that it's reasonable the recognise a Dragon type (maybe not knowing that it's a wyvern), even though they are probably quite rare, just because of fables, etc.
Added to that is what would characters know of the powers of monsters. For instance, what sort of roll would be needed to know that a troll regenerates? What about that a troll is susceptible to fire and acid? I would think that this information can be given based on how much a PC suceeds at a recognition roll - eg, get 5 above the DC of the roll and you get some knowledge of a Special Attack or Special Defence.
On top of all this, there is personal experience for a character - should we expect the players to keep a list of all creatures that character has fought? What if a SA or SD wasn't used in a fight? Should they just keep a list of anything they noticed about particular combats - that just means the paperwork gets too much, IMO.
So, all in all, it's a more difficult question than one would guess.
I hope that my points at least made sense
Duncan