The naive way would just be to send a transaction to the recipient’s wallet address (or more practically, their ENS name) where the transaction payload is an encrypted text message.

As you point out, that requires both parties be on the blockchain. If you want to send/receive off-chain, you would probably just set up a trusted relay. e.g. send an ethereum tx to emailrelay.eth and it would forward it over the SMTP system. Send an email from a SMTP client to [email protected] and it’ll do the reverse. This implementation would have the relay see all your plaintext messages. Not much different from how centralized email services like gmail operate, in practice.

There’s nothing that makes any of this technically infeasible to a knowledgeable dev today — maybe it even already exists (ethmail.cc shows there’s at least interest in it). Transaction fees kill this from a practicality point of view. Probably you want to roll this out on a layer 2 network, and those are still pretty new things.