the ipod looks at what has changed in the itunes library and updates it accordingly. Therefore, it deletes any songs that have left your library since it last updated.
You cannot delete songs on the itunes library and keep them on the ipod unless you use manual syncing.
You can do this by changing the ipod options to manual update. This means that you have to (I believe) drag and drop which songs you want and delete songs you dont want on the ipod off the ipod itself.
If I was you, I wouldnt delete the songs completley anyway. You can retrieve songs off your ipod, but if the ipod messes up, you want have the songs on your ipod or your computer.
Back up the songs to an external HD if you are going to delete them, then you can always get them back should you need them.