1. Are the customers legitimate? Do you have a Spam module installed that is potentially blocking the person?
2. So they cant get past shipping correct? If they dont then i would suspect that the address the person is using might not be compatible with the shipping method, especially if your customer still receives other orders fine. By this what i mean is say they are at a business address and are attempting to use fedex home delivery.