Hi folks,
We have implemented Google reCaptcha (http://www.google.com/recaptcha/captcha)
to website of one of our customers who have such problem. He is testing it for a few days and informed me that it works ok. Well all who have the same problem can submit a ticket to helpdesc and get new reCaptcha.

Also I have solution for this request:
Is there anyway of preventing user to register an account if they list for example certain cities in the registration box?
I suggest using currency converter plugin which detect visitor country by IP, having visitor country name you can prevent him to use registration.

John