In the case of Tor, the objective is to obtain a valid circuit relatively quickly so I feel that even exponential backoff would need a low max time to be practical.