Hola rachpts; yo lo que hago es crear un código alfanumérico aleatorio cuando el cliente solicita la nueva contraseña y lo guardo en la BBDD asociado a ese ID de cliente; en el enlace incluyo el ID del user (como haces tú) y ese código, de manera que, cuando se conecta, comprueba que ese user tiene ese código y le deja modificar el pass.
Una vez hecho, cambio el código por un 0 y ya está.
(Obviamente, si un usuario se conecta y el campo "cod_cambio" es igual a 0 no le permite cambiar el pass...)
Ej: $mensaje.= " http://www.midominio.com.mx/recupera/usuario/pass.php?usuario=".$usuario."&cod=45r6a12 \n";
Si se entra con http://www.midominio.com.mx/recupera/usuario/pass.php?usuario=".$usuario."&cod=0 directamente no permite acceder y si el usuario no tiene el código indicado tampoco
Es simple pero efectivo.