The BIP44 gap limit approach is a weak or even broken concept for recovering BIP32 based wallets.
It makes an assumption about the use case of a BIP44/BIP32 based wallet.
The default limit of 20 (some even use 5) will quickly lead to lost funds in recovery if the wallet was used in non-super-trivial use cases.
The missing metadata in a BIP39 mnemonic or in BIP32 xprivs tend to make recovery complex and has a moderate risk of missing funds.
The ultra-safe(est) way to recover a BIP32 seed without metadata is to derive all possible keys (impossible) and all possible scripts, then, rescan the blockchain. But yes, your guess is right,... this is infeasible.
So how to recover?
If you develop a wallet or rescan tool, use a very large gap limit. Maybe 1'000 or 10'000.
If you are just a novice user?
- Well, just make sure you keep your old backup in case you detected lost funds.
- Don't purely trust a BIP32/39 recovery, make sure all your funds are there
- If not, consult an expert (watch out for fraud, use a trusted person), or research how to extend the gap limit and how to derive multiple script types
- If you are using Electrum, read here about the gap limits and ways to extend it