My way of addressing that part was to simply ask what the most complicated thing was they ever programmed, and then to ask one or two follow up questions about that. I've got enough field experience that just by asking that one question I'd be able to come up with a follow up question that would nail a 'poser' in one go, if the answer was satisfactory I'd let it go at that and assume they're telling the truth, if not then I would ask one or two more follow up questions and by then I'd usually know for sure if someone is fibbing or just nervous (people can be very nervous during interviews, the bigger problem to me always was to not discard 'good' people that are simply nervous and botch answers to questions rather than the fear of hiring the wrong person because they manage to bamboozle me).
Another thing I did was to take as much time as I wanted during an interview, I would schedule at most one interview per half day just to make sure that I didn't have to cut an interview short. This made the interview process more relaxed and on the whole gave me enough time to figure out what made someone tick. Most interviews were over very quickly anyway, but every now and then it took a long time to get a feeling for whether or not someone would fit.
One of my biggest discoveries was that when hiring someone good that they would refer their friends, and they would be pretty critical about who they'd refer, screening out a lot of potential duds for me without any effort on my part.
In the Toronto office we ended up hiring four guys that already knew each other previous to joining the company.
This can also work against you, another 'group of friends' applied and I would have been happy to hire just one of them, he stuck with his friends instead.
I once hired a guy that just wanted to learn how to program but did not yet have the ability. This was a risky move, because as a startup you don't really have the time to invest a lot of it in to a person that is not yet proven. But it worked out very well, and Jeffrey actually was one of our most reliably productive people, in part because we gave him a chance that probably nobody else would have.
Sometimes having a will and a drive trumps technical ability.