I’ll note that much as one can use an SMS infrastructure to assert that a person has at least temporary control of a mobile phone you could use the existing notary system.    A service provider prepares a document instructs the user to print it, have notarized, and return to the service provider.

I wonder if that could be done in a manner that avoids revealing to the service provider any information other than the information contained in the document.  For example, could you keep the user’s name out of the service provider’s hands.