If a user logs on before all the programs have been replicated throughout the enterprise, some Start menu icons will be missing.
When that user logs on subsequently, the missing programs are not populated because the software installation extension knows that the policy has been applied.
To resolve this problem, change the automatic install state, or some other small change, to force the policy to be re-initialized on the client computers.
NOTE: DO NOT perform a redeployment as this may remove the programs while the user is using them, causing data loss.
The best practice for assigning large numbers of programs is to wait until users will not be logging on and logging off during the replication time frame.