I have found that the biggest problem is lies about a person's skills. Lies about where they worked and what they did are generally less relevant. A person can have references that check out no matter how careful you are, but they are still incompetent. They simply went from job to job being totally incompetent.
Trusting people will bring you problems. Never trust a candidate. Don't let someone deceive you because they get you involved in an interesting conversation - this could all be staged to prevent you from asking questions. Wasting time with candidates who are essentially trying to defraud you is also a problem. Be ready to end the interview early.
This is especially problematic with sysadmins. I believe that about half of candidates submitted by the best headhunters or filtered by careful HR departments are completely lying about the skills on their resume (90+% if unfiltered). They are usually telling the truth about where they worked - they just were allowed to be incompetent at the previous job. Since I've seen incompetent employees allowed to last for years at a job, this isn't a surprise.
What I do is:
Bring the resume to the meeting. Ask them the simplest possible question about every skill they mention. If it's DNS, ask what an A record is. If it's C, make them write Hello World. If they mention "Linux", ask for an example of a disk device name or name a very well-known configuration file and ask what it's for (e.g. /etc/fstab). If they can't answer a trivial question immediately and confidently, they are a liar. The interview is over, hiring a liar is always problematic. They will lie throughout the job. It's like going on a first date with someone who instantly reveals themselves to be a pathological liar. Make sure they knew it was on their resume (that a recruiter didn't add it).
If the stress of being asked a trivial question about one of their skills is something they can't handle, they're not going to be able to handle the stress of a small project, let alone a production emergency. Sometimes the undue stress is from people with poor social skills, I don't judge people for simply showing signs of stress. But if they suddenly can't function, it doesn't matter what the cause is, they won't be able to do the job. They're lying about the skill, even if they can do it in some situations they can not do it in a real-world situation. If their language skills are too poor to communicate an answer, the interview is over. They're lying about the skill. "DNS" is an abbreviation for "able to configure and maintain DNS in response to requirements", being unable to communicate with others about the requirements means you do not possess the skill. If someone is poor at communicating, I try to determine how much of a problem this is, therefore how much of an impact this would be on their ability to do the job.
Explain to HR that you will end the interview early if they are lying about skills on their resume. You don't have a responsibility to make a person who is lying and trying to defraud your company not feel embarrassed that they were caught. Your environment will dictate how to handle this. The safest way is to say that you're going to send in the next interviewer. Shake their hand, tell HR that the person was caught with material lies on their resume, and to have them escorted out of the building. This reduces the risk of a violent confrontation. Remember these people are already trying to scam you - they indeed might escalate the situation.
If they get through this, you ask the next level of question about -each- skill. (you can do it in two passes to save time if you're suspicious, one pass if they seem legitimate). Some hands-on (give them a keyboard) testing is required for the second pass. If it says DNS on their resume, ask them how reverse DNS is handled, or what a PTR record is for. If it says C on their resume, give them a keyboard and have them write a program with flow control that actually compiles. If it says Linux, give them a directory full of files and ask them to rename some and delete others. Depending on the context and the severity of the problem, you may want to continue if someone fails on the second pass - e.g. if the skill is not needed for the job. "I used to know it and forgot" should not be acceptable at this stage. You're still asking questions so simple that a person who claims to have forgotten it and listed it as a skill is lying.
The next step to making sure their resume is honest is discussing their previous job experience. If they can't talk confidently about things they claim to have done and put on their resume, they are lying. Sometimes it's extremely poor language skills - too bad, the job requires communication and an inability to communicate is a legitimate reason to not hire someone.
After you've gotten through this point, the real interview can begin.