In my opinion Authorize.net is the best payment gateway out there.
Also to quote their FAQ's:
Does Authorize.Net support
international transactions?Yes.
Merchants can submit transactions to
the payment gateway on behalf of
non-U.S. customers. To do so, the
merchant's bank account must be with a
financial institution located in the
United States, and the merchant must
be configured to accept the customer's
card type: Visa, MasterCard, American
Express, Discover, JCB, Diner's Club,
or EnRoute. The payment gateway will
submit the amount of the transaction
to the customer's card issuer, who
will then handle all currency
conversion to U.S. dollars. Since
default Address Verification Service
(AVS) settings may cause foreign
transactions to be declined, merchants
who plan to regularly accept
international transactions should make
sure that their AVS settings are
configured to meet their business
needs.
So this is the one I would choose and it is not very hard to implement.