Costruisci la condizione where facendo qulcosa del genere:
codice:
//....
list($first, $last) = explode (" ", $search);
$construct .="cognome LIKE '%$first%' AND nome LIKE '%$last%'";
$construct .=" OR cognome LIKE '%$last%' AND nome LIKE '%$first%'";

$construct ="SELECT * FROM registrazione WHERE $construct";
$run = mysql_query($construct);

//...
Considera anche la possibilità di rendere i campi cognome e nome FULLTEXT così da poter usare MATCH AGAINST e ordinare i risultati di ricerca per attinenza.