IMHO se l'utente chiudesse il browser c'è poco da fare se non è stato autenticato, e quindi il risultato potrebbe essere memorizzato in una sua area riservata, ma la vedo dura.
Una cosa che si vede in certi siti è l'avanzamento (barra) del processo, probabilmente per disincentivare l'utente ad andarsene. Una cosa che a occhio potrebbe essere veloce da fare è quella di cambiare e mostrare lo stato tra una exec e l'altra.
Tempo fa avevo fatto delle ricerche ed avevo trovato che con le ultime versioni di PHP è disponibile la programmazione parallela (quindi è meno sequenziale come anche tu scrivi, però metterà molto più sotto pressione il server), ma sfortunatamente è un argomento che non ho avuto modo di sviluppare.