I assume you're talking about Allshare (DLNA), correct? And you've tried the answer I gave over here: http://forums.cnet.com/7723-13973_102-566335/samsung-tv-shows-deleted-files-on-external-hdd/
This is a different problem from the one on that thread. With that thread, you have a mass storage device connected and the TV is indexing the files. So by resetting the TV, you flush the cache. Allshare works differently. You have a piece of software on the PC that displays to the TV what files it has to share over the network connection using Allshare. So what program are you using on your PC to share the files over?
I have problem with my Samsung TV PN51D800, its a software problem for sure, I have 2 PCs connected via wifi to the TV, I have video files on these PCs and I watch them on the TV, when deleting few Files from the PCs their names still appears on the TV files list!
Samsung Tech told me to reset TV to original setting, I tried this 3 times with PC off, with wifi off and with both off, all didn't work, but Samsung cancelled my request for service because they don't know how to Fix it!