I know MusicMatch and PressPlay have the disappearing songs (and both are almost dead now anyway, AFAIK). I'm not sure of what the terms on the new Napster are, I'll ask though.
iTunes has a Windows client now for their store, although it's still pretty nifty by itself. On the University network, there are several people that share their libraires, and you can stream from them at no cost (other than bandwidth, of course). So if you really want to listen to a certain song, and don't feel like owning it, you can look through others' shared libraries, or if you want to find some new music, or etc. Only thing is you have to search through each individual library, you can't search across all of them
.