I think this is a pretty common theme. Should there be published guidelines and API restriction on how links are integrated or should we simply count on plugin authors to make sensible decisions in regards to UI?

IMHO this is partially what separates the men from the boys so to speak. Quality plugins get more downloads. A portion of what makes a quality plugin is how it's integrated into the whole of WordPress.

Personally I always opt to add the plugin settings under the section where it most directly applies. As Steven Bradley mentioned, there are only a few instances when a plugin should create a top-level menu.