Which menu should a third-party module choose, between "Structure" and "Configuration"? I noticed that some module prefers to add their menu items under "Structure," while other modules prefer to add them under "Configuration."

I thought that the reason of choosing "Structure" was because the menu items were related to some kind of "entities," but I then noticed that Rules is adding its menu items under "Configuration." 
Vice versa, Views and Flags put their menu items in "Structure."

What is then the criteria to use when deciding under which menu a module put its menu items? Does the "Structure" menu contains only menu items that are related to content?
This and many other D7UX related things are best explained in the UI Patterns session from yoroy and Bohjan: Drupal 7: Interface patterns.

In short, Structure is meant for structural things which are used regularly (mostly during site building). If those modules add their stuff their and are not Views, Panels or similar, chances are that they are doing it wrong. :)

Not everyone exactly agrees on the IA (Information Architecture) of Drupal 7 yet or simply doesn't know about it. Not even Drupal 7 core is very consistent IMHO; I don't think the contact.module settings belong to Structure, for example, when not even those from path.module are, which are most likely way more often used.