Depth-first search schemes are known to be more cost-effective for solving graphical models tasks than Best-First Search schemes. In this paper we show however that anytime Best-First algorithms recently developed for path-finding problems, can fare well when applied to graphical models. Specifically, we augment best-first schemes designed for graphical models with such anytime capabilities and demonstrate their potential when compared against one of the most competitive depth-first branch and bound scheme. Though Best-First search using weighted heuristics is successfully used in many domains, the crucial question of weight parameter choice has not been systematically studied and presents an interesting machine learning problem.