Basic problem: any situation involving authentication other than in person, to someone who knows you personally, is going to involve trusting some kind of document. I don't see a way around this — if you don't have a good relationship with the offical trust system of our society, or anywhere to securely store small objects, you're just as screwed now as you would be under my system. I'm trying to define a document that can be used in a manner similar to existing ones, but isn't replayable. I hope I've established that it's better than the current system, where all the relevant documents can be replayed without even trying to crack anything.

As for proving you're you to your credit card company in order to report a stolen card — what, you don't have a backup? Without a backup copy of your card number (as on a monthly statement), how would you do that now? You'd probably also have a couple of questions on file with your credit card company (and not on the widget), answers to which would be sufficient to suspend (but not to reactivate) a stolen key. You'd only need to visit a notary if you needed to re-bootstrap onto the official trust network from scratch (where scratch = personal acquaintance/physical presence).

A signature produced by a card might also identify the individual card (i.e. might also be signed with a key unique to the card, on top of your key), which would make it possible to revoke a card without revoking all the keys on it. You'd revoke the card+key combinations (you could do this over the phone, at least for your credit card key), and authorize a new set of card+key combinations (this, you would probably need notarization for).