OK so I was browsing randomly and noticed that one of the thumbnail images was just a trash can. So I clicked it and the intermediate image was just a trash can too. So I clicked that and nothing happened.
So I looked around, and a number of images were like this, so I went into the admin tools and ran "Update thumbs and/or resized photos" with the setting "Everything: full-sized, resized and thumbs".
This simply resulted in the missing thumbnails being gone completely (just tiny squares) and the intermediates for them still being trash cans.
So, I deleted the ones I could find and instructed my website's staff to do the same if they find these images.
Then, I was browsing again and found that some of the images have thumbnail images and also intermediate images, but the full size image appears to be missing. When I hover over the intermediate image there appears to be no hyperlink, just like with the trash can intermediates.
I don't rummage around in the gallery's files deleting images or anything like that. We have moved the website a few times such as between servers. I couldn't see any obvious permissions problems although some of the thumbnail and normal images were set to 644 (most are 777).
This is concerning because whole albums seem to be missing their full size images and I don't know why. Others have lots of full size images.
Thanks a lot for your time, guys