For account recovery in store verification is viable. They're already collected data on their customers via payment processors.

I would also force users to watch a video explaining the security features and quiz them before turning them on. You can't expect users to immediately understand how the security model works.