Military operations typically involve cooperation of varioius military, government and commercial organizations from various nations. In order to coordinate these autonomous organizations, a social mechanism is required that facilitates deliberative planning and task allocation in decentralized, open environments, and enables agreements via a legal contracting process. In this paper, we present (a component of) such a mechanism, called the Legal Agreement Protocol (LAP). Agents that plan using LAP must plan with partial observability - that is the customer is only aware of proposals (capabilities) that suppliers choose to send. This makes it difficult for the customer to determine the (minimum/average) expected cost of any unallocated sub-tasks in its search. In this paper, we present and compare various heuristics that allow the customer to dynamically determine the expected cost for sub-tasks as proposals are received during planning. We show that different heuristics have tradeoffs in terms of quality of solution and search effort (efficiency of search and quantity of communication). The number of distributed agents involved in planning also influences the effort required to search. More agents increase communication, but provide more information (observability) about agent's capabilities to be utilised by the heuristics.