activation through email

Hi everyone I have a site with around 1000 new users everyday, and when every user register my scripts will send a random password to his email. the problem is that I got many users (specially hotmail users) complain that they didn't receive any email (even in the hotmail junk box). I know that hotmail is filtering me as a possibly a spammer (because I use a shared mail server) and there is nothing I can do about this. now I stooped sending the password to the users email and I just make the user chose his own password and he can login directly without the need to check his email for the password. but the problem now is that many users are registering with a fake emails :( so I want to ask you if you have any solution for this ? how can I (in someway) make my scripts check if the email is valid and exists email before I register him without the need to send any password or activation link to his email ? do you have any idea ? Thanks -- echo "Hello World :)"