Maybe they FedEx the password to your physical address on file. Maybe they contact all phone numbers and emails they have for you and say "someone has requested an emergency override, if you object call us back in the next 4 hours." Maybe they do a Skype session and compare your photo to the one they have on file.
All this costs money, of course. That's the price of doing business.
Do you tell the user on signup to print an in-case-of-emergency-break-glass password which is only ever to be used to get into a locked account and other special circumstances?
It may seem over the top but seeing as it's unique across service providers, I think it's a hell of a lot better than the overly abused "what is your mother's maiden name" type questions. I consider these questions to be in the same boat as sharing passwords between websites (since they are)!
(And if someone has managed to break into both your personal email account and your business's online-banking account, getting your web-host to recognize you will be the least of your problems.)
Consider a determined attacker. A posted signed letter has zero cost and is easily forged and a phone call is free via Skype. There's plenty of low-tech ways to circumvent security.
