How did you delete them, from the player itself or attached to a computer? Note that if you connected to a Mac, you must empty your Trash while the player is still connected, otherwise only the reference to the files on the Mac will be deleted, not the files themselves.
Reloading firmware will do nothing, but if you want to delete everything and have a clean slate, you can format the player. There is an option to do this in the Settings menu.
