Que tal
kireta, en primer lugar te recomiendo para tu paginación utilizar una librería como el
Paginator, muy util y poco complicada para lo que necesitas, segundo lo que puedes hacer es tu validación por número de cédula(Ya que sería un número de identificación único) no así lo mismo con los nombres y apellidos que es inevitable que no se presenten dos usuarios que repitan esa información, antes del INSERT a la BD haces un SELECT a tu tabla y verificas con la función
mysq_num_rows(), que el número de filas sea igual a cero si es así, realizas el INSERT.
Saludos.