File recovery software don't work very well with video in my experience. It sounds like you don't have the drives though, so that's your first step. I'm not a lawyer, but if the gas station is saying the footage is already deleted then you will have a very hard time convincing a judge to force them to hand over drives.
We can get access to the DVR system easy enough. I suppose your recommendation is identify the drives (as in hard drives?) as opposed to the DVR make/model itself?
And then look for file recovery software they seems to work well with said hard drives?