In addition to the searches recommended by terdon, you could also search by the folder name.
So if someone deleted (or moved) the files using a wildcard, you may not find any of your filenames specified in any history file.
For example, if someone did:
$ cd /home/mydir
$ rm *
$ cd somewhere-else
$ mv /home/mydir/* .
You wouldn't find any of your filenames in their history, but you would find
So, also try:
grep 'mydir' /home/*/.bash_history /home/*/.zsh_history
Also: I don't know if it's possible, but perhaps this happened as a result of some automated cleanup after exceeding disk-quota. That would be a pretty brutal policy, but I suppose it's possible and it might be worth investigating.