If you are not capable of identifying these people without spending hours of staff time and engaging in whiteboarding exercises, something is very wrong in my opinion. The person you're describing will not be able to pass a thoughtful 15 minute phone screen, and that's if a phone screen even happens because this type of candidate probably doesn't make it past a resume review if the person reviewing the resume is qualified.
In the case of a phone screen, I honestly find it hard to believe that folks have so much difficulty believing that it's possible to get a good sense of a candidate's skill and knowledge without sitting over his or her shoulder and watching him or her code. A phone screen is a conversation. In most cases, a candidate who is faking it will have a very hard time describing in technical detail his or her work, and answering technical questions about his or her work.
Start with candidates who have good resumes. Ideally get code samples and/or a portfolio. Prepare for your phone screen so you can ask good questions. It really is that simple.
If you take the time to review a resume thoroughly and ask thoughtful technical questions about a candidate's past work in the phone screen, the phone screen is almost always going to be a painful and embarrassing experience for a lying candidate. And such a candidate will virtually never make it past a reference check.
The problem is that most companies are lazy. Hiring managers don't read resumes closely and wing it (i.e. jump on phone screens without preparing). Reference checks? What are those?
People can memorize the key features of OOP, but still not be able to use it. So do you not hire new grads? Do you never hire someone with an extensive background in C, because you dare not quiz anyone and you don't want to risk hiring someone who can't really ever get a handle on OOP? Are you going to pay the total cost of all these people, who probably won't last 3 months?
What's even sillier is that I bet most people, given the option, would prefer to try solving some small problems for a short period of time if they knew it could help their chances of getting the job. Why wouldn't you if you knew you were competent?
You're right, phone screens usually get them, but not always. A fair number can still make it through.
Do you have any advice for how I can deal with that better?
You should also be aware that hiring requirements are more the wish list of the hiring organization than hard requirements; that is to say, don't "feel bad" about not quite meeting the requirements. If you're close, go ahead and apply. Come in and shine in the interview and only hiring organizations with poor business skills will ignore that you've only got 2 years instead of 3 in Python. (Such exist, though, sadly.)
However, I don't know myself how to deal with people who get too particular. When I'm writing my requirements, generally all my requirements come out as "Blah years of experience in $TECH_WE_USE or similar", and even then I'm really only saying "years of experience" because it's the standard; what I really mean is "a level of skill commensurate with what you'd usually expect after Blah years", but I can only deviate from the standard so far, you know? I don't know what to do about interviewers/organizations who think that 5 years in Perl translates out to 0 years of experience in Python. (All you can really do is comfort yourself in knowing that they're really hurting themselves with such specificity, though.)
For those of you who are early in your career, be sure to keep trying new things out every so often. It's really easy to get trapped because it sneaks up on you; you shouldn't be trying something new every week, because you need some depth, but if you've gone a year with nothing new tried, you may be in some trouble.
And be sure your "something new" is a new type of thing, not just a new thing. Learning Python, then PHP, then Ruby, then Perl, is really just learning one thing, maybe 1.5 things. You ought to be learning a dynamic language, then a static one, then maybe SQL, then learning about reliable cloud programming, then perhaps a full functional language, then perhaps go write a GUI with a conventional GUI toolkit, then learn some dynamic front-end Web programming, write a compiler, write a network app starting from sockets, use SSL for something serious, etc. etc. IMHO, the truth is that the programming world doesn't move that fast, but part of the illusion that it does is that it is quite a big bigger than meets the eye at first. It looks like it is moving quickly because there are things that look new to you all the darned time. But under the hood, progress is actually pretty slow.