Mmmm.... ho fatto un pò di prove.
In effetti, la cosa migliore da fare è:

a) determinare quali tipi di file accettare
b) creare una cartella protetta del web server in cui inserire un "esemplare" per ogni tipo accettato
c) con un semplice ciclo, ricavare le "firme" (ad es. i primi 16 byte) di tutti i tipi accettati, ed immagazzinarle in una tabella di database
d) ad ogni upload di file, fare fopen($_FILES['file']['tmp_name'], 16) e verificare se è presente nella tabella

Non sarà perfetto, ma insomma