The list of programs on the left hand side of the Start menu is really two lists. (You can see the separator line between them.) The top list is the so-called "pin list". This is the list of programs you picked to be "locked" to the top of the Start menu. You can "pin" a program by right-clicking it and selecting "Pin to Start menu", or you can just drag it directly into the pin area.

The bottom list on the left hand side of the Start menu is the "most frequently used" section of the Start menu, which selects the programs you have used the most in the past month or so.

If you right-click an item that happens to be in the Start menu's pin list (either by right-clicking it from the pin list itself, or by right-clicking the original), one of the options is "Unpin from Start menu". If you select this option, then the item is removed from the Pin list.

If you right-click an item on the "most frequently used" section of the Start menu, one of the options is "Remove from this list". If you select this option, then the item is removed from the "most frequently used" section of the Start menu. As far as the Start menu is concerned, you never ran that program. Of course, as you start running the program subsequently, it works its way up the popularity chain and might break into your "most frequently used" list based on your usage after you removed it originally.

The difference, then, between the two, is that each removes the item you clicked from a different list. One removes it from the pin list, and the other removes it from the "most frequently used programs" list. There is a line separating the two lists, but most people don't realize that the line is there for a reason. It's not just a pretty face.

To make things less (or perhaps more) confusing, if you select "Remove from this list" for an item from the pin list, it also removes it from the pin list as well as removing it from the "most frequently used programs" list.