Hola, buenas.

No soy un gran experto en captchas pero lo que estás comentando tiene dos soluciones: o bien utilizas ajax y reescribes el captcha o bien vuelves a hacer otra llamada al server para refrescar la página: no hay solución milagrosa a este respecto.

Un ejemplo de captcha bastante fácil de usar lo tienes en la página de jcaptcha de sourceforge; en él aparece como configurar el web.xml para que el servlet de la aplicación te lo recargue cuando haces una llamada a servidor.

Espero que te sirva de ayuda. Un saludo.