When I graduated college (UC Berkeley, very large public school in California) I had to go to the registrar to pick up my diploma since I graduated off cycle. In line in front of me was a guy who seemed to know the lady at the window well, and put down a piece of paper and said "got another list to check". The lady went into the back, so I asked the guy what he was doing.
He told me he worked for a background check company and was there about once a month with a list of names to verify graduation dates. He told me a lot of his work comes from government and big companies. He then suggested that if I was going to lie about graduating, make sure it was to a small company that can't afford background checks!
He also told me that almost every month there is at least one person who fails to have the degree they claim to have.