One way I've used hashes is to set the verified user's cookie to be something like:

$cookie = $user_id . $delimiter . hash( $user_id, "host secret passwor
+d" );
[download]

So on subsequent user accesses, all I need to do is split on the $delimiter and run $user_id, "host secret password" through the hashing algorithm and compare against the hash in the cookie to verify the user.

I haven't look at the code at everydevel, but it looks like perlmonks does something similar to this.

This trades a (slow) database access for a (slow) hash computation, so I'm not sure if there's a real winner (or if there is, it'll be system-dependent.) Just another option to consider ...

Also if you run a large site with millions of users, your source of entropy can be depleated quickly, negating any security you would have gained.

That's really an academic debate. I should argue that your scheme depends on security of MD5 algorithm and therefore cannot be more secure than MD5. History shows that even cryptographic hashes has some problems, and if I recall correctly, some of the MD-series hashes did have problems.

OTOH, my scheme depends only on security of server, and if attacker can read data from server's database, it will not look at nonce, but directly at the target data stored here. Authentication is here not only for authentication itself, but for data protection, and there is no point making authentication stronger than protection of data itself.

And if I have large site, my entropy pool gets exhausted by SSL subsystem in the firts place, so I will need HW crypto-card (RND-generator) anyway.