I am experiencing the same problem. I posted on ReCaptcha website this problem, and I received the following response:
Are they wildcard subdomains?
If so, you could get a global key for *.domain.com and use that for your child sites.
I tried setting a global key for my website, but it didn't work. I also read the instructions for WP MU 3.0.2 (http://wordpress.org/support/topic/cannot-install-recaptcha-plugin-for-multisite?replies=16). I tried this, and it didn't work. I had to go into Cpanel and undo the coding.
I am still searching for an answer.