I would check the following:
- Make sure that the Catcha is marked as a required field. This will simply check that something (anything) has been entered. The captcha validation itself is sever side, so it need to do a submit.
- In the On-line form web part, check Ajax > Use update panel. The prevents the whole page from reloading, focusing instead on the form.