The first objects to arise in a cold dark matter universe present a daunting challenge for models of structure formation. In the ultra small-scale limit, CDM structures form nearly simultaneously across a wide range of scales. Hierarchical clustering no longer provides a guiding principle for theoretical analyses and the computation time required to carry out credible simulations becomes prohibitively high. To gain insight into this problem, we perform high-resolution (N=720^3 - 1584^3) simulations of an Einstein-de Sitter cosmology where the initial power spectrum is P(k) propto k^n, with -2.5 < n < -1. Self-similar scaling is established for n=-1 and n=-2 more convincingly than in previous, lower-resolution simulations and for the first time, self-similar scaling is established for an n=-2.25 simulation. However, finite box-size effects induce departures from self-similar scaling in our n=-2.5 simulation. We compare our results with the predictions for the power spectrum from (one-loop) perturbation theory and demonstrate that the renormalization group approach suggested by McDonald improves perturbation theorys ability to predict the power spectrum in the quasilinear regime. In the nonlinear regime, our power spectra differ significantly from the widely used fitting formulae of Peacock & Dodds and Smith et al. and a new fitting formula is presented. Implications of our results for the stable clustering hypothesis vs. halo model debate are discussed. Our power spectra are inconsistent with predictions of the stable clustering hypothesis in the high-k limit and lend credence to the halo model. Nevertheless, the fitting formula advocated in this paper is purely empirical and not derived from a specific formulation of the halo model.