But that has nothing to do with deterministic wallets. Non deterministic wallets do not require address re-use.
The reason that clients reuse addresses is because random key wallets are unsuitable for general use.
Requiring users to update their backups after every n transactions results in permanently lost funds.
The solution is to implement BIP32.