I used my profile as a test as this seems to happen to all profiles on the network.
I had a folder in My Documents that I no longer needed. So I deleted it. About two hours later I rebooted my computer and sure enough, not only did that come back to my profile, but also did 6 items I deleted over a week ago from my desktop.
How do I keep them from coming back? Is there a setting on the server I've overlooked?