Well, you have plenty of options:
1.) Set a cookie saying that he's registered. Then just do a check to see if they have that cookie. This can be good because it can be done silently without the users knowledge.
2.) Use a session if you want to allow them to register again after they close their browser window. Not as good a solution if you want to disallow them completely.
3.) Log their IP in the database. Easiest solution. Although, with many ISPs today, the IP addresses change daily or upon each connection. So you can't be guaranteed that they don't sign-off and back on again and re-register.
You should definately do the verification email version. It's a valuable asset to any site and it helps to prove that they didn't use a fony email.