Perhaps you should think about the number of times you've entered a new shop to find some present for someone. Refusing the first sale because the shipping address is different equals to saying FU to most gift orders in my opinion.

As a side note, the most heavy handed and dumb fraud detection processes I ever saw where fom very small shops who would for instance try to hand mail or phone you to have you fax them some doc.

It's a real PITA, but since someone taje time to communicate with you in a people to people level, usually I wouldn't just cancel, and try to make it work out.