Normally when using the card with an official payment gateway, a reported, stolen credit card should be marked as unusable. The card will be refused by the gateway.
If you really need advanced authentication before allowing a card to be used by the client, you should verify his identity by making the client send you a copy of his ID card or passport and a recent bill (water, electricity,...) which states his name and address. This address should be the same as on the credit card. Do note that this will make transaction a lot more difficult and cumbersome and make some clients go away.
Also make sure that when performing credit card transactions you are completely PCI-DSS compliant if you have to be. If your business is not PCI compliant there are various measures that the card brands can take, ranging from warnings and monetary fines to revoking your ability to process transactions entirely. More importantly, the PCI DSS allows you to assure your customers that you're protecting their credit card data appropriately. In case of a breach you can also be held legally liable by your customers.