Condense your Knowledge Skills into as few as possible. Then start using Knowledge Skills as an excuse to give players bonuses between +1 to +4 for just about everything they do. Limit this to a number of times per game session decided by you.
Condense your Knowledge Skills as much as possible to about no more than 5. As an example, the Knowledge Skills 'History, Local, & Nobility' could be condensed into a single 'Knowledge Historical' type skill.
Next, improve the value of Knowledge Skills by allowing them to grant players 'Favorable Condition' bonuses to anything they do, whether it's making a different Skill Check, Attacking, Improving their AC or making a Saving Throw. Any time the PCs do anything, get yourself used to asking, "How would a certain Knowledge Skill help this PC gain a bonus on her attempt?" As an example, if a PC Wizard casts Charm Person on an Orc, a successful Knowledge Arcana check might improve the difficulty of her Saving Throw by a +2 Favorable Condition bonus. Flavor it any way you can. You'll soon realize that you can come up with a reason for almost any Knowledge Skill to give PCs a Favorable Condition bonus.
When you do, be careful not to overdo it. On average, give each PC a bonus like this the same number of times as his Knowledge Skill per game session. For example, a Cleric with 5 ranks in Knowledge Religion might gain a bonus to anything he does that can be affected by that skill 5 times each game session. Depending on your campaign, that frequency might not be suitable. If it isn't, simply reduce the number of times you do this per game session without making Knowledge skills useless again. For example, you might give your PC's this bonus once for every 2 ranks they have in a Knowledge Skill or even once for every 5 ranks. If a player has ranks in three separate Knowledge skills, he'd be gaining more of these bonuses with each game session than a player who doesn't.
Also make sure these bonuses stay isolated and help only that specific PC. It should never branch out to another PC.