Signing an offer letter, to me, is very old school - it's not a legally binding document that says, "You must come work for me for x days" as we all know. The offer letter is really more for the candidate - it spells out clearly what your opportunity is. It's their last chance to have
you spell out the job, perks, and PTO on paper. So his/her signing the offer letter is really his/her mentally saying to themselves, " What he said on the phone and during the interview is represented here - no surprises... This is a good opportunity. It fits me. I'm doing it."
The part that sucks the most is the you sent out the rejection letters already. I think that's just sort of "par for the course" sometimes. It will happen to you always and forever. I had someone sign my letter, show up and work for one day, and then email me at 9:00AM the next morning to tell me that she had re-joined her previous job as the head manager. She had told me during our interview that her boss really wanted to keep her but just couldn't come up with the money. Well, clearly the boss came up with the money and more. What can you do? Nothing. You start over. Yes, you can go back to your other candidates but I tend to not like doing that. After all - this was the best candidate. Why settle for #2? I'd rather just start the whole process over and find someone else completely.
My advice: have good training and solid policies in place that help you churn faster. Also have solid hiring plans and work hard to uncover what you can. It will pay off in the long run.