[GraemeJ]

A quick and dirty way would be to put all the songs you need in your set into Audacity (free) as separate tracks and then normalise the gain on each one so that it's just below 0dB e.g. -3dB (to prevent peaking). 

NO!

That is not the solution to the problem.  There is a big difference between simply normalising a batch of songs to the same peak level and making their relevant loudness the same.  If you only normalise all the tracks to the same level, there will still be a difference in perceived loudness and the initial volume problem will remain.

The way to do this is to use a program such as MP3Gain, as noted in an earlier answer.  This will set the perceived volume of each track relative to the track you pick as your 'standard.  For .wav files, there is a program called Volume Balancer which achieves the same end.

Actually, having re-read the OP, I'm not sure if this is his problem.  He seems to be saying the volume is different on a second play of the same track, which seems to be very strange behaviour to me.