I had this same issue plague me on a Windows Media Server (SAN Media Server) 6.5.4 recently so thought I would add an additional step I took to fix my issue.
I have 2 libraries attached to this media server. And whenever there was a reboot, I would sometimes see that 1 of the libaries tape drives were all ok, the other had MISSING_PATH entries.
In the past, everytime I saw this I did a delete of the problem path drives in the Admin Console GUI and re-ran Device Configuration Wizard to re-add them with new/correct discovered paths.
Now prior to all this I had Disabled Removable Storage service. So this wasn't the problem.
However, since then I noticed in my System Event Viewer logs that I was getting 10005 errors.
At this point , my problem drives were still showing MISSING_PATH entries in Device Monitor.
I started to look about the device manager on the media server and followed the steps to delete phantom and ghost devices in this technote:
DOCUMENTATION: How to delete "ghost" or "phantom" devices from the Windows Device Manager when using Veritas NetBackup
It showed up all the loads of ghost entries for my tape devices and Media Enclosures. So they were all removed.
Next, I followed the steps in technote
GENERAL ERROR: After disabling the Removable Storage service on Windows Server 2003, the system event viewer log reports Event ID 10005. NtmsSvc DCOM errors.
Did a reboot and MISSING_PATH is now gone. Did another reboot, all devices OK.
So if anyone else stumbles across this, problem you might need to follow the technote above as well as disabling Removable Storage service.