Actually we have things setup so the media libraries are under a specific folder for each site.
If there is a file in the directory, media library will show an import option because it is not in the db. I don't see this, so I'm certain the file does not exist. Also clicking on the links or the view icon from the Insert Link dialog returns a 404, so again I know the file is not there.
I'm wondering if a table got out of synch somehow. I do have aggressive caching, but this has persisted after an app restart.