Physicochemical models of signaling pathways are characterized by high levels of structural and parametric uncertainty, reflecting both incomplete knowledge about signal transduction and the intrinsic variability of cellular processes. As a result, these models try to predict the dynamics of systems with tens or even hundreds of free parameters. At this level of uncertainty, model analysis should emphasize statistics of systems-level properties, rather than the detailed structure of solutions or boundaries separating different dynamic regimes. Based on the combination of random parameter search and continuation algorithms, we developed a methodology for the statistical analysis of mechanistic signaling models. In applying it to the well-studied MAPK cascade model, we discovered a large region of oscillations and explained their emergence from single-stage bistability. The surprising abundance of strongly nonlinear (oscillatory and bistable) input/output maps revealed by our analysis may be one of the reasons why the MAPK cascade in vivo is embedded in more complex regulatory structures. We argue that this type of analysis should accompany nonlinear multiparameter studies of stationary as well as transient features in network dynamics.