It has been more than a year since this post on credit card skimmers, and, of course, the problem hasn't gone away, so an update seems in order. The latest wave of skimming attacks forgoes the overlays or modified replacement parts, and instead is wired in between the reader and the logic board. Wireless transmission of the skimmed data means nothing shows from the outside. This article from bankinfosecurity.com provides some interesting insight, including the brilliant concept of universal gas pump keys.
A much older article, but still quite relevant, is presented here on The Register. In this case the breakdown in physical security isn't even at the merchant's point of sale, but instead is all the way back at the head of the supply chain, perhaps even during manufacture. This approach compromised the European "chip and PIN" cards, which are much more robust in security protection than their typical US counterpart.
Without a dramatic increase in physical security, both at the point of sale and throughout the supply chain, this problem will not be solved.
In the mean time, if you must use one of these ultra-convenient terminals, force it to use credit mode rather than a PIN based debit mode. Most systems go out of the way to make this more difficult, as the debit mode is less costly for the merchant, but in general, the after the fact fraud protection is better when the credit card logo is involved. You will still get skimmed, but your financial recovery will be slightly less painful.
Complain to the merchants. Complain to the parent organizations. They have little motivation to fix this, and don't care about you and your financial wellbeing. And big media, expose the merchants; publicly humiliate them, and don't buy the story of the merchant as another "innocent victim." Without the pressures of consumer backlash and bad publicity there is simply no motivation to fix the problem. Remember that universal key, and note that it gives easy access to other people's financial data, but no access to the gasoline in the merchant's tanks. That isn't innocent, that is complicit.