Daniel_Reynard I was having the exact same issue today and it took me half a day to even understand the root cause. Thanks to this article and you identifying advertised shortcuts as a possible source of the problem, I came across this uservoice request: https://microsoftintune.uservoice.com/forums/291681-ideas/suggestions/20017999-retain-intune-cached-msi-with-out-auto-delete. Alas, there seems to be no solution in sight. It looks like deleting the msi from the mdm folder after install was deliberately introduced by MSFT a while ago, and they don't consider self-repairing packages relevant.
Anyway, I was able to solve the problem by editing the msi with the free edition of Master Packager. All it took was making the program shortcuts not advertised, and it immediately worked when deploying the updated package with Intune. Only downside is that editing the msi breaks the signature of the package, but that's something I can live with.