* if the postal code is a million miles away, flag it for manual review;
* check the IP address (and its ASN) and start identifying ones that are used commonly in chargebacks; if they're using a mobile device with a mobile network it's trickier, same if they're using proxies (though residential are harder to come by now that vip72 is no longer around)
* check if an email address actually exists and isn't just a carder's fresh email — like you said it's pretty obvious;
* don't deliver to person across the street;
* do some sort of phone verification/confirmation (and don't trust VOIP-type phones) (though this is still beatable, it's at least another cost to the carder).
Lastly, when you have a suspect order, don't tell them that you've cancelled the order due to fraud, or that you've found out: tell them that you're having trouble processing the order with the confirming bank and that you need them to enter another card. They will try again, burn some of their own money, and you'll have everything ready to go.
Querying your database and looking at patterns is certain to be helpful. Just a few joins and you can find a lot.
Happy to talk more offline to help you identify this better. Email in profile.