I don't think there's much you can do if you're cards get stolen at a cardstore or some other location though.
That's the rub--I'm sure this is how most cards get lost. Does anyone know if it's possible to get a rider specifically for the cards? I'm sure sport card dealers and so forth have some sort of provosion that protects them when they go to conventions. Furthermore, you limit for collectables through your homeowners/renters insurance might be less than the value of your collection.
Doing some searching, it looks like there are collection-specific companies out there. I wonder if they're worth it...
A freind of mine said that one of his friend's stax deck was stolen, but was insured so he just bought a new one. Thus, I am sure that some companies offer policies that would be applicable to decks. (and yes proof of ownership is important for house insurance stuff, although exactly what probably depends on your policy)