Quadratic unconstrained binary optimization (QUBO) problems have attracted considerable attention in recent years due to advances in quantum annealing technology, which is focused on solving them. Solving QUBO problems involves finding the global minimum of their objective function. Several classical preprocessing and solving approaches have been proposed in the literature, and in this contribution, we focus on the roof dual, a guaranteed lower bound on the global minimum of a QUBO. Importantly, in certain cases, the roof dual computation allows one to reveal the solution yielding the global minimum in addition to providing a valid lower bound. In this study, we develop an algorithm to solve QUBOs based on probing (that is, the exhaustive enumeration of certain variables). In particular, we show that probing sets of variables increases the probability of reaching the global minimum with the roof dual, and we prove a theoretical result that allows one to check whether the global minimum was found during probing. Although the runtime of the proposed algorithm is exponential, our empirical studies show that it allows one to find the global minimum of both random QUBOs and QUBOs for the Maximum Clique problem faster than brute-force enumeration and certain other state-of-the-art algorithms.