Debit card use is risky anywhere, especially on the road. KrebsOnSecurity.com recently ran an article regarding numerous ATMs in Mexico having skimmers on them, including at well known resorts. Credit card is far safer than debit.
With debit, one can come home and find their bank account overdrawn. Sure, the bank will restore the money (eventually; could be within hours or many days depending on bank and situation), but will the bank also reimburse all the fees charged by outside parties, such as credit cards, cell phone bill, etc... not necessarily. To digress, this is something to keep in mind when using billpay services. While many promise to reimburse overdraft fees to some extent, but won't cover other types of fees nor deal with other problems, such as having a card closed or cell phone service cut off, due to being overdrawn.
In my experience with various credit cards back in my better credit days, Amex was the most reliable abroad - no need to call in advance, never a block, and widely accepted in tourist areas. For places that don't accept Amex, one should carry a couple of different VISA / MC cards to play it safe in case one or more is blocked, skimmed, etc. As for what card issuers are best, I'm not sure it matters as much as it seems. My hunch, based in part on personal experience and reading the forums, is one's credit profile and level of actual usage (CL alone isn't a good indicator) plays a role in whether the issuer will take the extra risk and allow some questionable transactions through that they wouldn't for other cardholders.
