We present new, stabilized shape-perturbation methods for calculations of scattering from rough surfaces. For practical purposes, we present new algorithms for both low- (first- and second-) and high-order implementations. The new schemes are designed with guidance from our previous results that uncovered the basic mechanism behind the instabilities that can arise in methods based on shape perturbations [D. P. Nicholls and F. Reitich, J. Opt. Soc. Am. A 21, 590 (2004)]. As was shown there, these instabilities stem from significant cancellations that are inevitably present in the recursions underlying these methods. This clear identification of the source of instabilities resulted also in a collection of guiding principles, which we now test and confirm. As predicted, improved low-order algorithms can be attained from an explicit consideration of the recurrence. At high orders, on the other hand, the complexity of the formulas precludes an explicit account of cancellations. In this case, however, the theory suggests a number of alternatives to implicitly mollify them. We show that two such alternatives, based on a change of independent variables and on Dirichlet-to-interior-derivative operators, respectively, successfully resolve the cancellations and thus allow for very-high-order calculations that can significantly expand the domain of applicability of shape-perturbation approaches.