In my opinion, a function should throw an exception if it can't keep its "promise", if it has to break its "contract". The function's signature (name and parameters) determine its contract.
Given these two member functions:
const Apple* FindApple(const wchar_t* name) const;
const Apple& GetApple(const wchar_t* name) const;
The names of these functions as well as their return values indicate to me that in the case of FindApple the function is perfectly capable of returning NULL when the correct apple was not found, but in the case of GetApple you're expecting an apple to return. If that second function can't keep its promise, it must throw an exception.
Exceptions are meant for those exceptional conditions in which a function has no other way of reporting these conditions. If you decide to make it a part of the promise (read: function signature) then it can report that condition without throwing an exception.
Note that in the case of FindApple, it's up to the caller to decide how to handle the condition of "not finding the right apple" because it's no longer an exceptional condition.
You might be tempted to try to avoid all exceptions, but that means you have to account for all possible exceptional conditions, and you're placing the burden on the caller instead. The caller needs to check for "error conditions" then.
Ultimately, an exception needs to be handled, but only by the caller that knows how to handle a particular condition in a useful way. And I mean this in the widest possible interpretation: a service that gives up will try again later, a UI that provides a helpful error message, a web app that presents a "oops" screen but that recovers nicely, ... and so on.
Dave