Why are my photographs not stored with GPS location? I'm currently on vacation and used my Samsung Galaxy S 2 to take a couple hundred photographs.

I'm running the stable CyanogenMod 9 and have the Store Location option enabled in the Camera app. I also kept the GPS activated at all times.

Yet, most of my photographs were stored without location information which is somewhat disappointing.

I kept mobile data deactivated for long periods of time (to conserve battery power) and am wondering if that may have had an impact.
GPS has nothing to do with your mobile network (or Wi-Fi where applicable). GPS basically record the coordinates of the location (precise location) and time information. See the GPS tag or Wikipedia for more info. 

About you question, the reason that there is no location information for some photos is that the camera did not have time to contact the satellites. It takes some time (maybe 15secs or so) to establish a connection with the satellites and locate you. Did you suddenly opened the camera, took the photo? There is no time to establish a satellite connection. (I'm sure you did this to preserve the battery power). This is also the reason some photos in a row have their location recorded. Another possible reason would be that You might have been in a place where satellites couldn't locate you. (Indoors, thick forests, etc.)

If you really need the locations to be tagged for your photos, you can do it manually with your stock album app or third party app as well.

The reason some apps like maps use data connection or Wi-Fi is that they need it to download map data (road names, traffic info, etc.) So no need to worry about your data, GPS or camera. 

Hope this helps