In recent years, autonomous agents have been increasingly handling decision tasks on behalf of their human users. One such type of task with much potential to be carried out by an assisting autonomous agent is optimal stopping (e.g., in costly search). In such case, when it is the agent’s responsibility to decide when to terminate search, the challenge of maximizing user satisfaction with the process becomes acute. This paper provides evidence for the loose correlation between agent performance, profit-wise, and user satisfaction in this application domain, ruling out the use of the profit-maximizing strategy. As an alternative, it proposes a strategy relying on behavioral features. An extensive comparative evaluation of the proposed strategy, as well as the profit-maximizing strategy and the highest ranked strategy elicited through crowdsourcing reveals that the average satisfaction with the first is substantially greater than when experiencing with the others. The analysis of the results also reveals several important insights related to people’s ability to estimate the effectiveness of search strategies, satisfaction-wise, or propose such strategies themselves, contributing to the study of how human beings deal with optimal stopping problems in practice.