This work identifies the first lattice decoding solution that achieves, in the most general outage-limited MIMO setting and the high rate and high SNR limit, both a vanishing gap to the error-performance of the exact solution of regularized lattice decoding, as well as a computational complexity that is subexponential in the number of codeword bits as well as the rate. The proposed solution employs lattice reduction (LR)-aided regularized (lattice) sphere decoding and proper timeout policies. In light of the fact that, prior to this work, a vanishing gap was generally attributed only to full lattice searches that have exponential complexity, in conjunction with the fact that subexponential complexity was generally attributed to early-terminated (linear) solutions which have though a performance gap that can be up to exponential in dimension and/or rate, the work constitutes the first proof that subexponential complexity need not come at the cost of exponential reductions in lattice decoding error performance. Finally, these performance and complexity guarantees hold for the most general MIMO setting, for all reasonable fading statistics, all channel dimensions and all lattice codes. {\textcopyright} 2011 IEEE.