We observed SAX J1808.4-3658 (1808), the first accreting millisecond pulsar, in deep quiescence with XMM-Newton and (near-simultaneously) Gemini-South. The X-ray spectrum of 1808 is similar to that observed in quiescence in 2001 and 2006, describable by an absorbed power-law with photon index 1.74+-0.11 and unabsorbed X-ray luminosity L_X=7.9+-0.7*10^{31} ergs/s, for N_H=1.3*10^{21} cm^{-2}. Fitting all the quiescent XMM-Newton X-ray spectra with a power-law, we constrain any thermally emitting neutron star with a hydrogen atmosphere to have a temperature less than 30 eV and L_{NS}(0.01-10 keV)<6.2*10^{30} ergs/s. A thermal plasma model also gives an acceptable fit to the continuum. Adding a neutron star component to the plasma model produces less stringent constraints on the neutron star; a temperature of 36^{+4}_{-8} eV and L_{NS}(0.01-10 keV)=1.3^{+0.6}_{-0.8}*10^{31} ergs/s. In the framework of the current theory of neutron star heating and cooling, the constraints on the thermal luminosity of 1808 and 1H 1905+000 require strongly enhanced cooling in the cores of these neutron stars. We compile data from the literature on the mass transfer rates and quiescent thermal flux of the largest possible sample of transient neutron star LMXBs. We identify a thermal component in the quiescent spectrum of the accreting millisecond pulsar IGR J00291+5934, which is consistent with the standard cooling model. The contrast between the cooling rates of IGR J00291+5934 and 1808 suggests that 1808 may have a significantly larger mass. This can be interpreted as arising from differences in the binary evolution history or initial neutron star mass in these otherwise similar systems.