As far as I know, only the US uses AVS. (???)
We use authorize net as well, but I think we've relaxed the AVS rule. But we only ship to addresses that are the same as the billing address. Also be weary of rush orders in large amounts.
Not the best solution, but there is no real way to protect yourself from int'l fraud orders if you want to ship internationally.
at least with authorize.net.
also if you get fraud orders, I would suggest jotting down their IP addresses.