We present an exact generic method for solving the pricing problem in a column generation approach, which we call branch-and-bound column search. It searches the space of all feasible columns via a branch-and-bound tree search and returns all columns with a reduced-cost value below a certainthreshold. The approach is based on an idea from Krumke et al. (2002) for the solution of vehicle routing problems. In this work, we formalize and generalize this method such that it can be applied to a large variety of different problem classes. We further derive strong bounds to effectively prune the search tree, which allows us to significantly speed up the generation of columns and thus reduces the overall solution time. In addition, we show that our column search methods can be combined with lexicographic optimization easily and efficiently to solve problems with multiple objectives. Finally, the theoretical results are corroborated in an extensive computational study for two different applications: the sequence-dependent cutting stock problem and the optimized assignment of transport orders to employees in a hospital. On the basis of real-world data, we can show in both cases that it is superior to use the branch-and-bound column search as pricing algorithm in the presented restricted master heuristic than conventional column generation. In particular, for the second application the heurstic based on the branch-and-bound column search even outperforms both an industry-standard heuristic for the problem as well as a standard solver on a polynomial-size MIP formulation within a real-world problem setting.