Bid evaluation in a multi-agent automated contracting environment presents a challenging search problem. We introduce a multi-criterion, anytime bid evaluation strategy that incorporates cost, task coverage, temporal feasibility, and risk estimation into a simulated annealing framework. We report on an experimental evaluation using a set of increasingly informed search heuristics within simulated annealing. The results show that excess focus on improvement leads to faster improvement early on, at the cost of a lower likelihood of finding a solution that satisfies all the constraints. The most successful approach used a combination of random and focused bid selection methods, along with pruning and repeated restarts.