Registration Password Not Being Sent to Everyone

I just started having visitors register for my site. The vast majority aren’t having any problems. They get an e-Mail with their new password. However there is a significant number who are contacting me telling me that they didn’t get the password. I’ve been setting a temp password for them and sending it to them. There has to be a way to fix this problem — I just cant find it.