We calculate dominant cross section contributions for stau pair production at hadron colliders within the MSSM, taking into account left-right mixing of the stau eigenstates. We find that b-quark annihilation and gluon fusion can enhance the cross sections by more than one order of magnitude with respect to the Drell-Yan predictions. These additional production channels are not yet included in the common Monte Carlo analysis programs and have been neglected in experimental analyses so far. For long-lived staus, we investigate differential distributions and prospects for their stopping in the collider detectors. New possible strategies are outlined to determine the mass and width of the heavy CP-even Higgs boson H0. Scans of the relevant regions in the CMSSM are performed and predictions are given for the current experiments at the LHC and the Tevatron. The obtained insights allow us to propose collider tests of cosmologically motivated scenarios with long-lived staus that have an exceptionally small thermal relic abundance.