A method is disclosed for processing mobile-originated random access requests in a mobile telecommunications system that randomly selects new signatures for re-transmissions in the event that collisions have occurred. As such, the random access re-transmissions are randomized over the signature domain instead of just over the time domain. Consequently, the disclosed invention significantly shortens random access delays caused by collisions or erroneous arrivals at base station receivers, and also significantly reduces the interval between random access re-transmissions.