In the absence of data, it could be all or none of these problems. What makes these intermittent problems so unnerving is that if you haven't proven to yourself that you've identified the real issue, you are throwing darts in the dark, hoping that you've addressed it. Then you find yourself dreading the next phone call from the customer, yelling at you about not having fixed the problem.
What you need to have is some continuous monitoring of your video surveillance system so you can see whether the gaps in video are correlated with dropped packets, queue depth to storage, POE events or something else. In our data, a majority (>70%) of this kind of problem is configuration related.
Given that your cameras are configured to generate a significant amount of data even with compression, you need to check for load issues in your switches and servers. H.264 is a good codec but can be misleading if you've spec'ed the configuration assuming a level of motion that doesn't match actual experience.
Milestone (ONSSI) configurations have a particular problem in their Live-to-Archive migration regime if not configured properly. You need to measure how much video data is actually downloaded to the recorder and whether it is exceeding the capacity of the Live partition before it is migrated to the Archive partition. You may have it configured where it works most of the time but if you get more motion on some days, the amount of data may exceed the total capacity of the partition before migration. If that happens, the system will delete the video files from the Live partition prior to migration and you'll see these kinds of gaps.
Other times, we've seen situations where users are surprised to discover additional streams being pulled from a camera, recording to multiple servers unintentionally. Creating and managing additional streams can strain the camera's capacity.
Issues with fragmentation affecting performance of storage happens over time. Look at write queue depth and write latency for clues to those issues. If it is happening pretty soon after initial install, this is less likely the problem.
If you are looking for some technology that can help you monitor your installations, let me know.