Ok after reading the post that ikookmaar linked to and then putting in a lot of debugging steps I confirmed that the issue was/is definitely a matter of priority. (I also swapped to Better WP as a test and both have the same issue).
Following the solutions that fijnmedia identified, go to /plugins/contact-form-7/includes/settings.php line 17 and change
add_action( 'plugins_loaded', 'wpcf7');
add_action( 'plugins_loaded', 'wpcf7', 1);
After tracking through the debug calls I inserted I found that the call to function register_cf7() (or in BWP register_cf7_shortcode()) is calling wpcf7_add_shortcode(..) which in turn is testing to see if a global variable $wpcf7_shortcode_manager has been instantiated (as 'WPCF7_ShortcodeManager') before actually adding the shortcode. Turns out that the global had NOT been instantiated yet, so the shortcode wasn't added, and hence reCAPTCHA doesn't get processed. By adding the 1 to the 'plugins_loaded' action and raising the priority it effectively causes the global to be instantiated earlier.
Good or Bad?
I wouldn't have a clue, I am a DotNet programmer normally, in php I am just a hack :). Perhaps the cf7 plugin author or someone more knowledgeable can chime in?