Not deleting tracks from iPod

I stumbled about this quiet often now: When I delete tracks from my iPod nano (2nd Gen., 8GB) they are still there next time I mount them, even if I delete them from the library not only playlists. Usually the will be really gone when I delete them again.