("You used your debit card at an AM/PM in Washington State!!!!" Yes, I know, it is about 900 feet from my house; I go there regularly.)
Bank of America has an interesting optional feature where they geolocate the transaction, and if it's a certain distance away from your cell phone, it triggers the fraud process.
I think if more banks did this, it could cut down on a certain percentage of these problems.
The downside is that you have to trust your bank enough to let it track your phone 24/7. And having recently gone through the privacy notices of several of my bank apps and web sites, I'm not entirely sure that's a good idea, either.