Can you multiple file delete from normal locations, say some dummy test files in your My Documents folder ?
If this is purely confined to Publisher, we can look at that, but recycle bin corruption is quite common (and very annoying) so create a few test files on your desktop or in a folder of your choice and try to select several and delete them - see what happens and post back.
Of late. I have been worrying about possible HD failure because of crash and excess fragmentation problems. However it has been mostly related to my working on a single, large, very edited/altered Publisher file