Mandatory profiles

We have 9 PCs using a mandatory profile. For several months the programs on the start menu worked fine. Suddenly, some (but not all) of the programs are giving an error message that the shortcut link cannot be found. These programs are all installedlocally. Checking the profile, I noticed that all of the shortcuts link to one of the PCs directly. The only way I could fix the problem was to have the shortcut link of the problem programs point to the server itself. However, other programs workfine! Why would this happen all of a sudden?