Can't give any straight answer because it depends on the group, and the situation. For the example above, I'd only have the duke personally ask the players if they were well know, or this was happening in the middle of nowhere and the players were the only ones that could help. If neither of those were the case, I would say the duke couldn't find an experienced group to rescue his daughter, and that he issues a general proclamation.
The other options I might still use depending on the group. If the group was a bunch of hack and slashers I might just mention to them the cave of orcs. If the group liked to solve problems, then maybe I'd have them come across the ambush site, and see if that sparks their intrest. Or for that type of group they might find out that some seedy humans were meeting with the orcs and see if their interested in figuring out why. The overhearing the guard in the tavern I might use if the group needed a real push to be motivated. The last one about the evil duke, I would use on more roleplaying oriented group who would enjoy convincing the orcs to help them.