En qué formato tienes guardadas tus fechas?
Yo solo compararia fecha actual, y fecha limite (que es la que tienes en la variable $messmax
Código PHP:
mysql_select_db($database_Conexion, $Conexion);
$query_cumple = "SELECT Idusuario, Nombre, Apellido, Fecha_Nac, Sexo FROM usuarios WHERE Fecha_Nac>='".$dia_actual."' AND Fecha_Nac<='".$fecha_limite."' ORDER BY Fecha_Nac ASC Limit ".$Cantidad." ";
$cumple = mysql_query($query_cumple, $Conexion) or die(mysql_error());
$row_cumple = mysql_fetch_assoc($cumple);
$totalRows_cumple = mysql_num_rows($cumple);
O bien dale una leída a BETWEEN de mysql