In spacetimes with asymmetric extra dimensions, cosmic neutrino interactions may be extraordinarily enhanced by p-brane production. Brane formation and decay may then initiate showers deep in the Earth's atmosphere at rates far above the standard model rate, We explore the p-brane discovery potential of cosmic ray experiments. The absence of deeply penetrating showers at AGASA already provides multi-TeV bounds on the fundamental Planck scale that significantly exceed those obtained from black hole production in symmetric compactification scenarios. This sensitivity will be further enhanced at the Auger observatory. We also examine the possibility that p-brane formation resolves the GZK paradox. For flat compactifications, astrophysical bounds exclude this explanation. For warped scenarios, a solution could be consistent with the absence of deep showers only for extra dimensions with fine-tuned sizes well below the fundamental Planck length. In addition, it requires moderately penetrating showers, so far not reported, and ∼ 100% modifications to standard model phenomenology at 100 GeV energies. © 2002 Published by Elsevier Science B.V.