I've been thinking about this quite a bit of late, and I think it might not be a bad idea to have a minimum character level on some PrCs, coupled with a set of suitable other requirements.
So, for example, for a hugely sneaky PrC such as the Shadowdancer, I'd like to see a requirement of, say Hide 6 ranks, Level 5+.
I see a couple of advantages to this. Firstly, it means that there needn't be one true way to get into a class, as often seems to be the case (really, for the optimal Shadowdancer build, you need 5 levels of Rogue to start), and removes the silliness that can occur if a player picks up a lot of ranks in a particular skill late on, solely to get into the chosen class.
The final advantage is that I can introduce Prestige Classes to the campaign later on, without the PCs being ineligible since they haven't built their characters towards those classes since level 1. Or, alternatively, a PC can be designed to head towards one PrC, but then change direction due to campaign events, and end up following another approach.
(Take, for example, the Blackguard. Virtually no Paladin will ever actually qualify for this class, as it requires some feat and skill choices that just aren't going to happen. Yet this is one PrC that a fallen paladin should almost qualify for by definition.)