juste avant que ta page ne commence son traitement, tu affiche ton "veuillez patienter". Ensuite, va jeter un oeil ici : http://fr.php.net/ob_start.

Ca va te permettre de mettre dans un buffer...