Si ves este ejemplo, quizás te orientes un poco, como el captcha se genera a partir de una sesion de php, la validación se hace con php, sin embargo implementamos javascript para comunicar el resultado al usuario
http://foros.emprear.com/php/captcha/
Aqui algo más avanzado, que si bien la validación sigue siendo en el php, pasamos el form con ajax.
http://foros.emprear.com/php/demo-form-ajax-captcha/
En el caso de deshabilitar js, el form no se procesa
Son todas variantes
SAludos