Yes, it is expensive but possible to discover any funds associated with a seed, provided there are set limits to:
1. gap of address use (e.g. 20)
2. depth of hierarchy (e.g. 6)
3. gap in use of parallel branches (e.g. 0)
I would pick the limits in brackets above.
Maybe the solution is to have a defined way to import an unknown wallet?
This means that the gap space and a search ordering needs to be defined.
Given a blockchain and a root seed, it should be possible to find all the addresses for that root seed.
The hierarchy that the wallet actually uses could be anything.