ah. i thought you meant your library on your computer.
if you have purchased a song, and it is nowhere to be found (on your ipod/computer), you should go into your itunes account, to purchase history like you have already. next to the song, there should be a 'report problem' button. fill in the form, explaining, apple will pretty quickly get back to you, saying the song will be available to re-download next time you go into itunes.