I have a 30GB Creative Nomad Zen Xtra which does exactly what you are talking about. Now, maybe that is too much capacity for you, the other versions of the Nomad may also do this. Not only was the Nomad 10GB more than the 20GB iPod, it also cost $90 less. While it is a little larger physically, I much prefer the interface and the fact that I can use any software to manage it and not just iTunes.
I'm simply looking for an MP3 player where, when I am over a song, I can just delete it directly from the player.
Ipod won't do it and the iRiver 320 requires to you stop playing all usic (not just the song you are deleting and then navigate back to you music to start playing agin.
Anyone know of a playe that'll do it? Any and all suggestions are apprecaited.