no entiendo todavia donde esta la complejidad, disculpame...
con esto verificas si el registro existe o no.
Código PHP:
$sql=mysql_query("Select * FROM tabla_clientes where md=$md");
$datos=mysql_fetch_array($sql);
if(!mysql_num_rows($datos)){
//cliente no existe
}else{
//cliente existe.
}