The greeting and voice name files are stored in \commserver\streamfiles and are named using the alias of the subscribers or call handlers they're associated with - it's pretty easy to go fish around in there to find what you're looking for.
I'd be curious if you could go look for the greetings and voice names for a user that lost theirs in this directory and see if you can find them - if you find them in here but they aren't offered over the phone then the database is indicating they don't have a greeting recorded and we can take it from there. If the WAV files are missing I'd wonder what process might have done that - in this case the greeting paths for the subscribers will still "point" to a file in here and will likely throw errors in the event log when they try to play and fail.
If you've done backups with DiRT or a tape backup package that included that directory it's pretty straight foward to restore the greeting files themselves - they're just straight WAV files, nothing fancy. But you may have to past them in manually from the SA to get the database to point to them properly again - depends on what you find above...