Virtual Network Embedding (VNE) has attracted a lot of attention in the last decade. Nevertheless, recent analysis demonstrates that the performance of VNE solutions in key metrics like VN acceptance ratio decreases drastically with medium-to-large sizes of substrate and virtual networks. This paper proposes a constraint management approach that grades the quality of VNE candidate solutions according to the degree of fulfillment of their constraints and exploits this information to drive the metaheuristics to more promising regions of the search process enhancing their performance. Through simulation and formal statistical analysis, our approach has been proved to enhance VNE acceptance ratio practically at no time overhead. Formal statistical analysis and comparison with the literature demonstrate that our approach enhances the quality of embeddings and that such enhancements are more accentuated in large sizes of substrate networks, where the performance of standard metaheuristics decreases drastically.