We analyze the spectral efficiency performance and limits of orthogonal frequency-division multiple access (OFDMA) cognitive radios (CRs) with an imperfect availability of cross-link knowledge. In particular, in contrast to the conventional `average' and `worst' cases of channel estimation error in the literature, we propose a stochastic approach to mitigate the total imposed interference on primary users. Channel-adaptive resource allocation algorithms are incorporated to optimize the cognitive system functionality under transmit and interference power constraints. An expression for the cumulative density function (cdf) of the received signal-to-interference-plus-noise ratio (SINR) is developed to evaluate the average spectral efficiency. Analytical derivations and results are confirmed through computer simulations.