At one of the WordCamps (Boulder I think) Jane was talking about this very subject. She suggested that plugins should attach themselves where it makes the most sense. For example if your plugin deals with comments you would add your menu under the top level comments menu.

She suggested that very few plugins should ever add a top level menu. For things like ecommerce plugins it would make sense to grab a top level menu, but for most plugins it wasn't necessary.

It would be great if there were some guidelines in the codex about where to hook your menu. It really is a mess now.