The main problem under consideration in the present paper is the relationship between the rate of convergence of the recurrence coefficients, and the rate of decay of the exponential weight at the endpoints of the orthogonality interval \((a,b)\) (finite or infinite). In particular, for the weight \[ W(x)=\exp \left(-\exp_k(1-x^2)^{-\alpha}\right), \qquad x\in [-1,1], \] where \(\alpha>0\), \(k\) is a positive integer, and \(\exp_k\) denotes the \(k\)th iterated exponential, the authors prove that \[ \tfrac12-a_n=\tfrac14 \left(\log_k n\right)^{-1/\alpha} \left(1+o(1)\right), \qquad n\to\infty, \] where \(\{a_n\}\) are the recurrence coefficients for the orthogonal polynomials \(\{p_n\}\) associated with \(W^2\), and \(\log_k\) denotes the \(k\)th iterated logarithm. More general non-even weights on a non-symmetric interval are also studied.