Yes, there is a service which contacts the institution you put down to see whether you graduated or not.
Had trouble at a non-aviation positon once (temp agency for office work). They were unable to verify my BA even though I had it. Turns out someone goofed on the check and eventually it came back legitimate.