Para el caso que planteas tienes dos opciones:
1) Pre-cargar arrays javascript con todos los posibles resultados de las combinaciones de resultados que obtengas de todos los casos de las listas dependientes que intervengan.
De esta forma sobre-cargas al cliente por qué le envias -todas- las posibles combinaciones que obtengas. El proceso de "selección" se lo pasarías integro al cliente (por qué con PHP generás el código javascript de esos arrays o métodos que use Javascript para poder hacer la selección "dependiente").
Ejemplos: cualquier script que veas que funciona así en javascript .. podrías adaptarlo al uso que menciono generando dinámicamente las "líeneas" de código que sean el dato que use Javascript.
2) Usar técnicas de "remote scripting".
En este método se usan iframes ocultos que son empleados para "zona de intercambio" entre tu script PHP que se le pide x script que arrojará su resultado y la parte javascript (bastante) que le pasará el resultado al elemento (select en tu caso) de la página padre (de tu formulario).
Tienes ejemplos en:
http://www.ashleyit.com/rs/jsrs/select/php/select.php
Un saludo,