Secondo me ti conviene fare una pagina html(o php) (con la scritta "attendere") che richiama via ajax la pagina php che fa il lavoro. Quando termina lo script (success di ajax, se usi jquery) cambi il messaggio.
flush() andrebbe bene, ma devi fare i conti anche con il buffering dei browser (che tra l'altro non sono tutti uguali)