Symptoms

The reCAPTCHA module gets errors back from Google servers. The captcha is always telling you The answer you entered for the CAPTCHA was not correct.

Technical background:

You run a Drupal 7 site that has been upgraded from Drupal 5 or Drupal 6. These older Drupal versions have set 'arg_separator.output' = '&' for unknown reasons in settings.php. The settings have been removed from Drupal 7 core default.settings.php and will not exist in clean Drupal 7 installations. PHP by default sets 'arg_separator.output' = '&' and the Google reCAPTCHA library used by the module uses PHP http_build_query that use these setting to build URL query strings. With this invalid setting every webservice request to the Google server is broken as urls query parameters are separated by & and not just &.

Solution:

Drupal 6:

Remove or disable this line in settings.php:

ini_set('arg_separator.output',     '&');

If that doesn't work, you can also try changing the line to just have an ampersand, like so:

ini_set('arg_separator.output',     '&');

Drupal 7:

Replace the following code snippet in settings.php:

/**
 * PHP settings:
 *
 * To see what PHP settings are possible, including whether they can
 * be set at runtime (ie., when ini_set() occurs), read the PHP
 * documentation at http://www.php.net/manual/en/ini.php#ini.list
 * and take a look at the .htaccess file to see which non-runtime
 * settings are used there. Settings defined here should not be
 * duplicated there so as to avoid conflict issues.
 */
ini_set('arg_separator.output',     '&');
ini_set('magic_quotes_runtime',     0);
ini_set('magic_quotes_sybase',      0);
ini_set('session.cache_expire',     200000);
ini_set('session.cache_limiter',    'none');
ini_set('session.cookie_lifetime',  2000000);
ini_set('session.gc_maxlifetime',   200000);
ini_set('session.save_handler',     'user');
ini_set('session.use_only_cookies', 1);
ini_set('session.use_trans_sid',    0);
ini_set('url_rewriter.tags',        '');

with below code snippet and you have a Drupal 7 settings.php and the arg_separator.output no longer collides:

/**
 * PHP settings:
 *
 * To see what PHP settings are possible, including whether they can be set at
 * runtime (by using ini_set()), read the PHP documentation:
 * http://www.php.net/manual/en/ini.list.php
 * See drupal_initialize_variables() in includes/bootstrap.inc for required
 * runtime settings and the .htaccess file for non-runtime settings. Settings
 * defined there should not be duplicated here so as to avoid conflict issues.
 */

/**
 * Some distributions of Linux (most notably Debian) ship their PHP
 * installations with garbage collection (gc) disabled. Since Drupal depends on
 * PHP's garbage collection for clearing sessions, ensure that garbage
 * collection occurs by using the most common settings.
 */
ini_set('session.gc_probability', 1);
ini_set('session.gc_divisor', 100);

/**
 * Set session lifetime (in seconds), i.e. the time from the user's last visit
 * to the active session may be deleted by the session garbage collector. When
 * a session is deleted, authenticated users are logged out, and the contents
 * of the user's $_SESSION variable is discarded.
 */
ini_set('session.gc_maxlifetime', 200000);

/**
 * Set session cookie lifetime (in seconds), i.e. the time from the session is
 * created to the cookie expires, i.e. when the browser is expected to discard
 * the cookie. The value 0 means "until the browser is closed".
 */
ini_set('session.cookie_lifetime', 2000000);

If you cannot find the arg_separator.output setting in settings.php it may has been set in your php.ini and you should better revert to the PHP default value.