Is there a way to read a subimage from a stored texture? My google-fu has failed me. All I can find is that you need to read the entire texture back which is really slooooow.

Have you tried copying the subimage from the stored texture into a smaller texture? Maybe it would work roughly like this: 1) Create a new texture the size of your subimage, 2) Attach this texture to a FBO for render-to-texture functionality, 3) Setup ortographic projection, 4) Draw the part of the stored texture you're interested in reading back, 5) Disable the FBO and switch back to perspective projection, 6) Read back the new texture with glGetTexImage.