It was vampires that got me on this, actually. Quite aside from monsters with templates, what do you do about NPCs with templates?
Vampires are neither super-common nor unusually rare, so the Knowledge DC would start at 10.
A level 5 human fighter with the vampire has a CR of 6 -- 4 from class levels, and +2 from the vampire template. So when encountering him, the party has to make a DC 16 Kn (Religion) check to recall one useful piece of information about vampires, such as that you really need Protection from Evil because they can dominate people.
But if the vampire was a level 10 fighter, he'd have a CR of 11 -- 9 from levels, 2 from vampire, and getting the exact same piece of information would require a DC 21 Kn (Religion) check.
It's weird that the difficulty of knowing the properties of a template varies depending on what kind of creature it's attached to.
And considering I pledged for the new edition of the Advanced Bestiary and have Hero Lab, templates are probably going to be popping up a lot more in my game. When I throw a swarmblooded teratocephalic gigantean house cat at my PCs, I want them to have a chance to figure out what the heck it is.