How is BIP 158 wallet rescanning supposed to work with xpub keys? A light client implementing BIP158 downloads filters and checks its addresses against that filter. If one matches, it downloads the block.
Now, let's say we have an HD wallet (BIP32), and/or an xpub key. How would we decide whether to download the block, based on the filter? Do we have to iterate over all possible derivations/addresses (potentially thousands) for each filter? Is there a more efficient solution?
No, you essentially have to do exactly that: test the block filter for each address that might have gotten used by your wallet. That might not be quite as bad as you seem to think, though.
Deterministic wallet backups usually come with a master secret and the derivation path. If you have both these pieces of information, only one derivation path needs to be searched.
Then, your wallet would usually generate a number of addresses in advance as a form of lookahead. The size of this buffer is often referred to as the gap limit. If any of the wallet's addresses appear in a transaction during the rescan, the buffer is refilled with additional new addresses before continuing to scan from that point on. The underlying assumptions are that addresses are generally used in the order they are generated, and that personal use of a wallet does not generate a lot of unused addresses. Therefore, light client wallets often employ a fairly small gap limit by default.
Some wallet backups additionally store the creation date of the wallet, which allows a rescan to ignore prior blocks than the corresponding blockheight.