A new branch-and-bound max-sat solver QTMAX integrates many of the best features of existing solvers to achieve superior performance, especially on larger benchmark problems. To challenge the solver, we adapted benchmarks from hard set-cover and vertex-cover problems. This work reveals the limitations of current solver technology and suggests the need for more sophisticated algorithms.