We describe a new method for the vehicle routing problems with constraints. Instead of trying to improve the typical metaheuristics used to efficiently solve vehicle routing problems, like large neighborhood search, iterated local search, or evolutionary algorithms, we allow them to explore the deeply infeasible regions of the search space in a controlled way. The key idea is to find solutions better in terms of the objective function even at the cost of violation of constraints, and then try to restore feasibility of the obtained solutions at a minimum cost. Furthermore, in order to preserve the best feasible solutions, we maintain two diversified pools of solutions, the main pool and the temporary working pool. The main pool stores the best diversified (almost) feasible solutions, while the working pool is used to generate new solutions and is periodically refilled with disturbed solutions from the main pool. We demonstrate our method on the vehicle routing problems, with variants respecting time, vehicle capacity and fleet limitation constraints. Our method provided a large number of new best-known solutions on well-known benchmark datasets. Although our method is designed for the family of vehicle routing problems, its concept is fairly general and it could potentially be applied to other NP-hard problems with constraints.