Well I found a partial answer to the question I asked right in Andreessen's essay, but it's not the one you give here.
I guess I think of the authentication of sender and content for recipients as being equivalent to the elimination of double-spending, and I don't see either as being responsible for the failure modes of fraud in digital payment systems. As a practical matter, recipients don't have has to question whether a particular person actually has the credit to complete a given transaction right now, and I'm not aware of double-spending credit as being a big problem for credit card payment systems. Who cares about solving that problem when we have a perfectly workable solution right now?
But sure, I get the point about other forms of fraud might be harder -- namely, stealing account information necessary to initiate transactions.
The question there is whether that problem too goes away in a world in which credit numbers are kept as private keys on a physical device (like a smartphone) and exchanged with merchants via something like SSH. Is the overhead of Bitcoin still worth it?