Earlier quoted context omitted.
I'm not sure how to solve this problem It's easily solved, banks and other institutions have been doing it for years. The solution is trivial, too: Require physical ID. In order to open a bank account you have to either show up in person, or provide equivalent proof (e.g. PostIdent). Why should it be different with cloud-services whose stated goal is to silo all your life's data? Why are they excused on lax security?
When I opened my Ing account I didn't need any of this. They verify your identity through a series of questions about your past, as well as your SSN. In fact, all US banks allow accounts to be opened over the 'net now. I've personally done it with several of them.
Still pretty good for now, though.
Edit: anyone know what the cost is per query for these services? I assume it's not free, thus likely not feasible for services that don't stand a good chance of providing enough revenue to offset the cost.