What type of file storing do you use?
In settings > System > Store files in
Database
File system
Database and file system
If on file system could you check if it's the file or the DB record missing (DB table: Media_File)
Do you have Web Farms enabled?
- if so does it happen on just one farm or all/multiple?