Did you reboot the client (player) apps themselves? My Android Shield player won’t update with new movie additions, so I have to kill the app and start it up afresh.
Does it show up still in a browser window? The browser is the best at updating as soon as a change is made, so if it’s showing up there then it’s a server problem. A Plex Dance (the steps you enumerated in your post) shouldn’t be needed. As soon as you have the library scan, the files should be detected as missing.
What I would try if I was in your spot would be to check to make sure there isn’t a duplicate of the files. If Star Trek shows up still, click the ... triple dot button and choose “Get Info”. See where Plex thinks the files are still at.
