How to prevent fraud attempts on Contribution pages?
How hard this will be depends on how determined the service abuser is to adapt to the defenses you introduce, and how easy a target your site is compared to other sites available to the attacker. If you are seeing a significant level of abuse, this indicates that your site is one of the lower hanging fruit.

Here are a couple of options I've seen have good effect -

fail2ban - We've used fail2ban effectively for assorted spam and abuse prevention. An approach to this looks like: 


Add a custom form validation hook to your contribute form.
In this hook, error_log to some logfile.
Add a fail2ban jail with this logfile which uses iptables to ban addresses that look suspicious.


There is a risk of banning legitimate IPs here, eg a single IP which many supporters sit behind (maybe you are a union and half your members are behind a certain corporation's firewall) or your own head office if they make a large number of transactions. So this is an approach to use with some considerations.

This approach is more effective if you are seeing repeat abuse from the same IP addresses; you can identify this by inspecting your webserver logs for the contributions (grep for POST requests hitting civicrm/contribute/transact then group by IP and count requests).

custom spam checks - I've seen form abuse drop off entirely simply by adding an additional required question. You can add this to your form, then use JS in your page to hide the field and populate it. This can be more effective than reCaptcha because reCaptcha is common enough to be worth automating for a botnet, but if your form is one of several they are outsourcing their CC checks to, then you only need to make your form less easy to abuse than others. 

This approach is effective against abuse where the attacking engine is less sophisticated than a web browser (ie lacks the JS engine in the browser). It's easy to test out.