IMO, if you shrunk a large (long), or medium creature such as a dire bear or human to one size smaller (now medium and small), I wouldn’t change the CR because the penalties for losing strength and intimidate penalties would be counteracted by their AC going up, “To-hit” going up, bonus to hide, and the ability to squeeze into smaller spaces would cancel each other out.
Now, the tricky part is when you shrink a large (tall) creature, like an ogre. An ogre without reach is certainly much easier to deal with as would a halfling creature that has been shrunk. The halfling would get no AoOs because he wouldn’t threaten and every time he attacked, he has to enter the target’s square which provokes an attack from the target. And with the reduced strength, creatures with damage reduction are way more difficult.
Once a creature is tiny and shrinks further, I’m not sure I would adjust the CR for the same reasons I wouldn’t do it for a direbear or human.
Be sure to take into account, smaller weapons do less damage then larger ones. Spells get tricky beause even though the sorcerer is the size of a brownie, his damage is that of a medium sized sorcerer and so while the hulk of a fighter only does 1-3 damage each round, the sorcerer can still do 10d6 with his fireball.
*brainstorm*
To determine the CR, what if you increased the monster as per the monster manual? Figure out how many size categories the party will shrink and what they will be fighting. Then “improve” the monsters until they are X size categories bigger. Give them all the goodies be being “improved” then, even though the party is tiny in size, and a rat too is tiny, the fight between them would be a medium/small sized party against a medium sized rat for the purposes of rolling the dice and keeping things easier on the PCs. Because the rat gained all those extra hp’s, the fighter doesn’t feel like he got screwed (because his damage should be 1-4 or so after his loss to strength and his bastard sword shrinking to the size of a dagger) and spells make more sense (like a fireball cast from a tiny spellcaster not doing as much damage proportionally as a medium sized spellcaster).
Regardless of what you choose, assigned Ad-Hoc values and keeping them fair is no fun and not easy.