potresti provare a far questo prima della query

list($dato_1, $dato_2) = explode(" ",$parolachiave);
$dato_1= trim($dato_1);
$dato_2= trim($dato_2);

SELECT * FROM utenti WHERE nome LIKE '%" .$dato_1."%' AND cognome LIKE '%" .$dato_2."%' OR cognome LIKE '%" .$dato_1."%' AND nome LIKE '%" .$dato_2."%'

se non ci sono risultati:


SELECT * FROM utenti WHERE nome LIKE '%" .$dato_1."%' OR nome LIKE '%" .$dato_2."%' OR cognome LIKE '%" .$dato_1."%' OR cognome LIKE '%" .$dato_2."%'

e vedi se ci sono risultati.

Un'po' lungo ma potrebbe andare.