I had one of mine stolen by a gas station years ago. They never had the card as I used the pay at the pump but they were able to get the info form their system and make a copy.
If your not using online banking then you need to sign up. I've had cards lost or stolen a couple times and never knew it until the monthly statement came in the mail. Since then I've signed up for internet based so I can check every day or so. It only takes a minute a day to just sign in and give a quick look.