Computational infrastructures for cooperative work should contain embedded agents for handling many routine tasks , but as the number of agents increases and the agents become geographically and/or conceptually dispersed, supervision of the agents will become increasingly problematic. We argue that agents should be provided with deep domain knowledge that allows them to make quantitatively justifiable decisions, rather than shallow models of users to mimic. In this paper, we use the application domain of distributed meeting scheduling to investigate how agents embodying deeper domain knowledge can choose among alternative strategies for searching their calendars in order to create flexible schedules within reasonable cost. In particular, we are interested in developing mechanisms by which agents can adapt their strategy choices to suit the demands imposed by a dynamically changing environment. In this paper, we first enumerate various strategies we have investigated to focus distributed negotiation between scheduling agents. Next, we demonstrate the necessity for such a scheduler to be adaptive in its choice of options for the various strategy dimensions, so that it can perform effectively over time. In order to build an adaptive scheduler that can effectively choose from available strategy options, we develop quantitative performance estimates of these options using detailed probabilistic analysis. Results from these analyses are used to provide guidelines to choose the most appropriate strategy combination given current environmental conditions and local problem-solving states.