Don't you guys have everything backed up on your iTunes or did you get some songs from someone elses iTunes? When you reformat, you will get everything back on your iPod, minus the stuff that is on your library.
You also might have some hidden things on your harddrive on the iPod. Just plug it in, go into My Computer and click on the iPod to see if you have files that are on there that you can delete.