Puedes hacer primero un select para comprobar si devuelve algún resultado y luego hacer el insert
Código PHP:
<?php
if(isset($_POST['alta'])){
$todo = $_POST['nombre']." ".$_POST['apellidos']." ".$_POST['email']." ".$_POST['departamento']." ".$_POST['extension']." ";
$nombre_apellido = $_POST['nombre']." ".$_POST['apellidos']." ";
$query = "SELECT * from `datos` WHERE `nombre` = $_POST['nombre'] AND `apellidos` = $_POST['apellidos']";
$result=mysql_query($query, $link) or die(mysql_error());
if (mysql_num_rows($result)!=0)
echo "<script type=\"text/javascript\">alert(\"Usuario ya insertado previamente\");</script>";
else {
$query="INSERT INTO datos(nombre,apellidos,email,departamento,extension,todo, nombre_apellido) VALUES('$_POST[nombre]','$_POST[apellidos]','$_POST[email]','$_POST[departamento]','$_POST[extension]','$todo','$nombre_apellido')";
mysql_query($query, $link) or die(mysql_error());
echo "<script type=\"text/javascript\">alert(\"Usuario Insertado Correctamente\");</script>";
}
?>