Stolen Credit Card Verification

So apparently someone decided that my web site would be a good place to verify their stolen credit card list.  He placed about a dozen orders with obviously false information.  Since my shopping cart is automated, it can't tell that "khkljhl" is any different from "john" for someone's name, so it just processes the orders.

I ended up blocking the entire C class of IP addresses where he was coming from (somewhere in .ae United Arab Emirates), and I'll have to keep an eye out for crap like this in the future.

I'd like to limit orders to 1 or 2 per day for each IP address, but that would mess up people behind big firewalls.  I could store their last order in a cookie, but that's easily circumvented by deleting the cookie between each order.

Can't think of a great solution except to keep blocking addresses when people do this kind of thing...