the skyboxes are less likely to be a memory constraint, and more likely to be a GPU time issue -- if they were right up against the border of 33.333 ms, lowering the resolution on a texture that (depending on the view) can fill up the entire screen is a really good way to quickly gain back some time.
granted, in those cases you'd typically expect that that's _all_ the GPU has to do other Cloud, because the screen is mostly just the one big skybox, but hey, who knows. i've seen stranger things.
(i guess maybe if the skybox was being drawn first the reverse would be true, because you'd draw it all before the occluding geometry is drawn (maybe because that geo has some transparent effects mixed in?!), but again, it's hard to say -- that'd be a pretty old-school way to go about it)