esattamente come hai fatto... l'unica cosa che devi cambiare secondo me è che devi selezionare non solo l'id, ma anche nome e data se vuoi fare dei controlli su questi campi... no?

codice:
$query = "SELECT id,nome,data FROM $tabella_utenti WHERE
 nome LIKE '%paolo%' OR
 nome LIKE '%marco%' AND
 data > "$inizio_oggi" AND
 data < "$fine_oggi"
 ORDER BY id";