Good question. The only reference I've found to those files is in `man insserv`:
/etc/init.d/.depend.boot,
/etc/init.d/.depend.start,
/etc/init.d/.depend.stop
The make(1) like dependency files produced by insserv for booting,
starting, and stopping with the help of startpar(8).
And in fact, running just plain `insserv` touches their modification time. So try that and see if it rebuilds them.
As a tip, when you are tempted to delete something like this for whatever reason, move them to a temporary trash directory instead.