You do not need to get the details why this is hard, just recognize that the only reason we have key birth date is because it reduces scan time. This lesson was learned while importing ordinary (WIF) keys or re-scanning the wallet.

Now, developers who implement a HD scan will recognize that birth date is not sufficient for reasonable scan time, but at least a look ahead window is needed to master the task and that eventually birth date might be re-set if start-index is also there. Certainly these assumptions require that the Wallet software that uses HD complies with that. I do not see why this would be a problem why is it important to protect freedom of key sequence use. The point of HD is to avoid key reuse and loss through missing backups. Both can be achieved even if there are restrictions on what key to use next.