I remember reading an article some time ago about the songs that get stuck in your head being of the form that they are repetitive, with minor changes from place to place. (If I can find a link, I'll edit it in) Furthermore, I learned about wavelet transformations somewhere along the line, and using them as a means of compressing data.

So here's my hypothesis: Might the brain store music in a manner similar to wavelet decomposition. Ie, instead of storing sound as a ".wav" file, it stores it with some generating algorithmic compression. The easier it is to regenerate the file, the more memorable it is. Thus what distinguishes music from noise is its dense compressibility. Perhaps this is why it's so easy to get songs stuck in your head, why you can remember songs after decades. Maybe it's even why it's much easier to "play" a song through in your head rather than just skipping around randomly between points.