Hola,
En teoria el flush si envia el HTML generado hasta ese momento (no se si influye alguna configuracion del servidor web, como la compresion de la salida con mod_gzip en apache).
Pero el problema esta en tu HTML. Algunos navegadores no muestran nada de una tabla HTML hasta que reciba el </table>, con lo que puede que el navegador haya recivido tu informacion, pero este esperando al </table> para mostrarla. Prueba con:
<table>
<tr>
<td>
cabecera
</td>
</tr>
</table>
<? flush()?>
<table>
<tr>
<td>
contenido
</td>
<tr>
</table>
a ver si asi te funciona.
Saludos.