I'm not sure when menu separators were invented. They could well have been dreamed up at Xerox PARC in the 1970s, although I can't find any definitive evidence of it. Apple included them in the design of the Lisa user interface; below you can see an example of menu separators looking pretty much as they do today in the Edit menu of LisaDraw, circa 1982.
LisaDraw running on the Apple Lisa, circa 1982
In common practice, a menu separator is used to break a menu into discrete chunks of related functionality. Usually drawn as a simple etched line, separators are thought to make menus easier to browse.
In Office 12, the Ribbon hosts controls which drop down menus. And many times we do still use plain old lines to separate sections in menus, just as designers did in 1982.
But we have another tool at our disposal that we use in certain menus as well: textual separators.
When a menu contains several discrete sections of loosely-coupled but related functionality, we use textual separators to show how the features in each section relate. The idea is that you should be able to scan the separators looking for the right section without needing to read every item in the menu. Here's an example of textual separators from a menu in the first tab of Excel:
We also use textual separators to categorize dropdown galleries for the same reason—to narrow down the set of choices you need to scan through. Here's an example from the new Office charting UI:
In places in which a textual separator would not be more helpful than a horizontal line, we do just use the line. In the LisaDraw menu above, for instance, putting a title "Editing Commands" over Clear, Duplicate, and Select All wouldn't really help to clarify the menu, so we would leave it off.
It's a judgment call when to use the textual separators, but we've tried to use them judiciously in Office 12 to clarify certain menus and galleries.