Distributed Constraint Optimization Problems (DCOPs) are well-suited for modeling multi-agent coordination problems. They involve a finite number of agents, variables and binary cost functions. The cost of an assignment of a subset of variables is the evaluation of all cost functions on that assignment. The goal is to find a complete assignment with minimal cost. Researchers have proposed several distributed search algorithms to solve DCOPs optimally. ADOPT and BnB-ADOPT are two related search algorithms essential for distributed constraint optimization. They exchange a large number of messages, which is a major drawback for their practical use. Aiming at increasing their efficiency, we present results showing that some of their messages are redundant. Removing most of those redundant messages we obtain ADOPT+ and BnB-ADOPT+, which in practice, cause substantial reductions on communication costs with respect to the original algorithms