The main thing to remember about UI is that all that really matters in the end is whether your design makes using your application or site a better experience for your users.
In the search example you list above you'll commonly see apps take two approaches:
- Put the search feature in a single location and allow the user to filter the search by selecting pending or accepted, or
- Put the search feature in both menus, already configured for the type of search to be done based on the menu it was launched from.
If you repeat the above choice for a number of factors you'll see a much more advanced (aka 'complicated') search interface for number one, and a much simpler (aka 'restrictive') search interface for number two.
Which one is best completely depends on your users. This is why many general applications have a simple search by default and a link to a more advanced search for those that want or need the additional capabilities; they're attempting to make everyone happy. There is absolutely nothing wrong with that if you're writing for a wide variety of people with different needs. If you're writing for a set of users with a restricted set of needs however, you can make some better choices.
In my experience your best bet is to work with one or two of your primary users and map out all of the steps they need to take to get each of the tasks the application will be helping them with accomplished. If there aren't a lot of branching points in that sequence of steps there shouldn't be a lot of choices or settings to make in the application; otherwise the users may feel that the app is harder to work with than it needs to be.
For the search example above, if the user has already navigated into the Pending Orders menu, the likelihood that they'll want to launch a search for Accepted Orders is very small and having to make that choice, or go elsewhere to do the search, will be an extra decision or action they'll need to take. Basic principle is if your user has already made a decision, use it; don't make them tell you again.
Use the UI you come up with as a first cut. Let your users, or a subset of them, try it out and make suggestions. If you have the option, watch them use it. You'll learn far more about how to improve the interface by seeing how they work with it than you will from what they tell you.