The readme/documentation for the Captcha module should point out that the #required field on a captcha element MUST NOT be set. That is, Captcha validation occurs entirely through the validate function, and there is no way to have an optional captcha.

$form['my_captcha_element'] = array(
'#type' => "captcha",
'#captcha_type' => 'image_captcha/Image',
'#title' => 'Captcha', // necessary for helpful error messages, otherwise #required error messages will be blank
* DO NOT set this to true: Captcha module will reset form_state[values][captcha] to ''
* which Drupal will consider an empty value and then fail the validation as #required.
* Lesson: #required is just a Drupal validation call for "must not be empty", not that
* the value is actually provided by another module.
// '#required' => true

Otherwise, Drupal will consider the field to be empty after processed by the module (I think the module sets a captcha ID instead?) and will NOT call any #submit hooks, but when the form is displayed the captcha won't be displayed (since the module considers it valid, the field is hidden) and no error message is displayed to the user.