We use a combination of BVJHK and Spitzer [3.6], [5.8] and [8.0] photometry to determine infrared (IR) excesses for a sample of 58 Large Magellanic Cloud and 46 Small Magellanic Cloud O stars. This sample is ideal for determining IR excesses because the very small line-of-sight reddening minimizes uncertainties due to extinction corrections. We use the core-halo model developed by Lamers & Waters to translate the excesses into mass-loss rates and demonstrate that the results of this simple model agree with the more sophisticated CMFGEN models to within a factor of 2. Taken at face value, the derived mass-loss rates are larger than those predicted by Vink et al. (2001A&A...369..574V), and the magnitude of the disagreement increases with decreasing luminosity. However, the IR excesses need not imply large mass-loss rates. Instead, we argue that they probably indicate that the outer atmospheres of O stars contain complex structures and that their winds are launched with much smaller velocity gradients than normally assumed. If this is the case, it could affect the theoretical and observational interpretations of the 'weak wind' problem, where classical mass-loss indicators suggest that the mass-loss rates of lower luminosity O stars are far less than expected.