Yes, that's normal behavior.
The all programs link on the start menu opens up a list of shortcuts to a number of programs. If you want to, you can edit that list to have more or less programs on it. You can change the names of the shortcuts and the order in which they appear. In other words, the all programs is not really a direct map into all the programs found in the programs directory. When a program is installed it creates a shortcut for itself and places it in the list of the selected user, or perhaps all users.
Which means that you could edit each user's list of programs. So that some users will not even see the programs available. And you can even make shortcuts and put them in the list of programs, and the shortcuts could be something other than real programs. And so forth that all non-blah blah blah.
In short, it's only a list of shortcuts.