I was always taught to look for the gaps of information in a resume.
For example, if the prospect lists three companies down their previous employers, I would try to find which of those had NOT been provided a contact or phone number.
And we were always taught to call the company as well as the individual referee. You'd be surprised that nearly all companies happily blast out information about an ex-employee, just simply by being asked.
They open themselves to a huge risk in doing so but they still do.
And calling someone "out of the blue" seems to be a lot more revealing than speaking to their supplied referees.
I mean seriously - if I get told one more time (when I speak to personal referees) that the biggest area of potential improvement is to get the prospective employee "not to do too much work" or "not to take on too many tasks" - like, hello????
But how to handle your issues?
I think you may be suffereing a forest v. trees issue. Each of these problems can be reasonably easily solved but take some work and effort to sort out.
Think about it like this - rather than think about the job, tell yourself that if you can get this information quickly you'll win the lottery and trillions of bucks.
Now do you have any new ideas?
So with the "old boss" issue - is he/she physically impossible to trace? Do you not have an ex-colleague, who knows someone, who in turn knows someone else, and that person had dinner with some other guy, and that last guy has your ex-boss's email address or phone number? Surely a few phone calls will sort this out.
Alternately can't you get another name of someone in the company who will validate your reference? From what you say about your references there must be someone else who'll attest that you're a pretty good find.
The degree . . .
The fact that the degree isn't a requirement for the job is now completely irrelevant.
What is now relevant is making sure that the information you readily provided can be verified.
With the degree issue surely there is more detail you can provide - college amalgamation, your own copies of your transcript as opposed to the bit of paper itself, old student ID cards, alma mater? Is there no-one - an old college friend - you are still in contact with who may be able to sign an affedavit (do you have them in the USA?) confirming that the college really did exist and you all went to it?
Is there zero record of the name of the college in Google or Yahoo? What about the Library of Congress or something?
There has to be a record somewhere and it can't take too much to find it.
Once you can verify that, it would seem to me that you are on easy street and should get the job.
Hey the birth date is a real tough one. I'd be very wary about that. You have given it now so again it exists and will probably be used.
I would have pointed out that if they needed to verify something with my birth date that can only be done once they have made me a job offer - the offer could be conditional upon the verification / validation and (as I understand it) that is reasonably legal. So they offer, you give birthday, they validate, you start work. Very simple.
{hey if your cousin is a lawyer and so you don't have expensive legal fees then this could be a real bonus fom heaven if you don't get the job }.