Buenas, yo personalmente añadiria algún otro dato que fuera mas personal y unico como un numero de telefono o una direccion de mail, algo que supiera que no se puede repetir, dado que en una ciudad muy grande, se puede dar la casualidad de que haya dos tipos que se llamen igual y vivan en la misma calle, pero eso es cosa tuya.
Como solucion a tu problema, podrias hacer algo asi:
Haces una consulta con los datos que te han puesto y si conciciden los cuatro haces el insert, si no le dices al usuario que hay un error.
Código PHP:
<?php
$consulta = mysql_query("select * from datos where nombre ='".$nombre."' and apellido ='".$apellido."' and calle ='".$calle."' and ciudad ='".$ciudad);
$resultados = mysql_num_rows($consulta);
if ($resultados == 0)
insert.....
else
echo "Tus datos ya estan registrados";
?>