Alan Cooper, in his classic interface design book, About Face, speaks directly to this question.
He points out, as you have, that there are multiple distinct techniques for issuing instructions to a program. He terms these, collectively, "command vectors." Menus are one type of command vector, as are toolbar "buttcons" (his term for toolbar buttons labeled with only an icon), drag-and-drop, and keyboard shortcuts (among others).
I call each distinct technique for issuing instructions to the program a command vector. Menus are a command vector, as are direct manipulation and toolbar buttcons. Good user interfaces will conscientiously provide what I call multiple command vectors, where each function in the program has menu commands, toolbar commands, keyboard commands, and direct-manipulation commands, each with the parallel ability to invoke a given command. This enables users of different skill sets and preferences to command the program according to their desires and abilities.
He argues that the primary purpose of menus is to serve as a pedagogic vector. In other words, they serve a teaching role because they are clearly labeled, explanatory, and present a catalog of all of the available options. Menus are also "safe," because users can easily browse all of the available options without actually invoking any of them. Finally, it is common for menus to display, in addition to a description of the command, the associated keyboard shortcut (if applicable). New users can easily ignore this information when learning the software for the first time, but as they begin to become more advanced, they will gradually discover it and begin to make use of it. Sure, this information could be buried in documentation somewhere, but that makes it harder to find and much less likely that anyone will ever read it. Taken together, all of these are compelling reasons why at least one of the command vectors must be a menu option.
But then, Cooper also points out that menus have a cost: they are slow and cumbersome to use for power users (or anyone who uses a particular piece of software frequently, becoming a sort of micro-expert with that software, even if they are not overall power-users when it comes to computers).
This is where the other types of command vector idioms come in, like toolbar buttons and direct-manipulation (like the +/– icons in a TreeView control). Keyboard shortcuts also fall into this category. They have the advantage of being quick and easy-to-use for power users, although they are not very clear or discoverable for novice users.
A well-designed UI should cater to all audiences. For anything but a throwaway, single-use application (for which speeding up experts is not an important goal), you need to provide both pedagogic and immediate vectors for the most commonly-used functions.
Both direct-manipulation and toolbar-buttcon command vectors have the property of being immediate vectors. There is no delay between pressing a buttcon and seeing the results of the function. Direct manipulation also has an immediate effect on the information without any intermediary. Neither menus nor dialog boxes have this immediate property. Each one requires an intermediate step, sometimes more than one.
In the same way that a stranger to town may take a roundabout route to her destination while a native will always proceed on the most economical path, experienced users of a program will commonly invoke a function with the most immediate command rather than the one that requires intermediate steps. Naturally, the most frequently used commands in a program are those that migrate onto buttcons in the toolbar. These functions are still supported by items on the menu—the menu command vector—where their use becomes increasingly the purview of beginners. Experienced users, however, gravitate toward the immediate vectors of buttcons and direct manipulation.
This bifurcation of usage along lines of experience is an important characteristic of software usage, and it affects how menus and dialog boxes are used. They are needed less and less for daily use, and have instead become a teaching tool for first-time and infrequent users.
The buttcons and other gizmos [controls] on the toolbar are usually redundant with respect to commands on the menu. Buttcons are immediate, while menu commands remain relatively slow and clunky. Menu commands have a great advantage, however, in their English description of the functions, and the detailed commands and data that appear on corresponding dialog boxes. This detailed data makes the menu/dialog command vector the most useful one for teaching purposes, which is why I call it the pedagogic vector.
This is all taken from Chapter 19 ("The Meaning of Menus"), p 278–80, in the book's first edition (© 1995). He goes on to say lots of other interesting and useful things in the chapter. I've tried to provide a concise summary of the observations most relevant to this question in my own words above. I'm not sure if he has changed his tune in the later editions of the book—I only have the first edition.
Even if he has, this still provides an illuminating historical perspective. Given Alan Cooper's influential role at Microsoft during this time (he is often credited as the "father" of Visual Basic), when the Windows GUI was evolving, it is reasonable to assume that many of the programmers and UI designers responsible for developing its characteristic idioms were strongly influenced by his opinions and perspectives.