Saddle points on high-dimensional potential energy surfaces (PES) play a determining role in the activated dynamics of molecules and materials. Building on approaches dating back more than 50 years, many open-ended transition-state search methods have been developed to follow the direction of negative curvature from a local minimum to an adjacent first-order saddle point. Despite the mathematical justification, these methods can display a high failure rate: using small deformation steps, up to 80% of the explorations can end up in a convex region of the PES, where all directions of negative curvature vanish, while if the deformation is aggressive, a similar fraction of attempts lead to saddle points that are not directly connected to the initial minimum. In high-dimension PES, these reproducible failures were thought to only increase the overall computational cost, without having any effect on the methods’ capacity to find all saddle points surrounding a minimum. Using activation-relaxation technique nouveau (ARTn), we characterize the nature of the PES around minima, considerably expanding on previous knowledge. We show that convex regions can lie on activation pathways and that not exploring beyond them can introduce significant bias in the saddle-point search. We introduce an efficient approach for traversing the convex regions, almost eliminating exploration failures, while multiplying by almost 10 the number of identified unique and connected saddle points as compared to the standard ARTn, thus underlining the importance of correctly handling convex regions for completeness of saddle point explorations.