If these keys are locally stored on your computer, how is an online-only recovery possible? How is losing the computer not a risk, or any local file to backup?
Your addresses (private-keys) are locally derived from the 12 word phrase that Exodus provides you when you backup your wallet. The email link (AFAIK) is also your word phrase but protected by both your passphrase and an Exodus 'key' (like explained in the page you linked). Your word phrase or private-keys isn't stored anywhere.
Are the keys not recovered with the e-mail link &/or 12 word phrase? (yes i'm aware you can export keys)
They are.