I wouldn't regard the usage of a deterministic wallet as "cheating", but of course a deterministic wallet comes with pros and cons of its own. But assuming that a reboot or sync is done by the user could be considered as "cheating". Basically, this would be the same as using a "regular" wallet software, and doing the private sync manually. I'm looking for something foolproof, where other components in the software stack can rely on every private key in use being persistently stored. If there is a deterministic wallet which enforces the sync in software, this would qualify (assuming that a deterministic wallet is applicable).
The sync only needs to be done once with a deterministic wallet because all private keys are generated from the seed. Actually with electrum you don't even need to sync. You have to write down the seed on a piece of paper as part of the wallet creation process so there's your backup. It is all you need to generate any and all private keys in that wallet.
Yes, I'm aware of deterministic wallets and how they work cryptography-wise. It would work in cases where the determinism is permissible. However, a setup process where you have to write something down would be bad for automating. Electrum, supplemented with a printer interface which blocks until the key has been printed out could work. But I understand that there is no ready-to-use solution yet which automates the process of having keys securely synced before being used on the network.