I linked to a tutorial of how the values work, but I'll summarize it.
The YYYY values are for the song you are using. XXXX is the stage + offset. The first song on Battlefield is 0000, and each song in the list after that is 8 later (in hex mind you). So the five songs on Battlefield have XXXX values of 0000, 0008, 0010, 0018, and 0020. Then Final Destination's first song is right after at 0028, and it continues like this through all of the standard stages, melee stages, and the menu. The stages aren't in the same order they are in on the stage select screen, but as long as you restrict yourself to the domain 0000 through 0750, always make the last digit a 0 or 8, and avoid 0688 (which is Hanenbow and probably not too dangerous to mess with though still generally not a good idea), you will be entering a legitimate value. The offset list, as linked to before, is here:
http://www.usbgecko.com/forums/showthread.php?t=257
I suggest reading what I had to say about some tracks in my previous post until the music list in the first post gets updated to be more informative, complete, and correct. That way you can know everything you need to know to work with the YYYY values in the domain 26F7-2835 which, to my knowledge, includes every useful track (though some not so useful things, like the victory music, are still undiscovered). Yes the YYYY values are the same as in the other music code; you're referencing the same list with both codes.
About unlockable tracks, I suspect they are just invisible with probability zero before you get them. They always appear in the same places once unlocked and function correctly online (which means that stage online loads that song in preparation for your opponent selecting it). It would, of course, be a really interesting experiment to alter a track and then unlock it and see if it reverts to the original track or is unlocked as what you changed it to. Of course, with various item spawn codes that can allow you to harvest all CDs trivially, I don't see why you wouldn't unlock all of the tracks first.
I haven't changed menu music yet, but I can answer the question about changing the main theme anyway. It would just change it in the menu when that track was selected; you are not replacing the usage of one track with another. What you are doing is altering what an entry in My Music is which, for some reason, stores the songs used on each stage in save data. That kinda suggests that Sakurai originally was going to make My Music WAY more flexible and let you assign any song you wanted to any stage (why else would the list save changes to it?), but I suspect the guys at Nintendo who decided not to send Mother 3 to the United States blocked it because they hate happiness. They then probably made sure four EarthBound tracks got removed and the new EarthBound stage would be laughably bad. Another theory might be that that feature would make matches online load somewhat slower, but I would think that would be minimal...
However, speaking of lists, the character list also needs to be updated to use their standard English names. That is, Robot -> R.O.B., Zako XXX to XXX Alloy, Pikmin & Olimar to Olimar, and by far the most important, Venasaur (which is wrong everywhere and a misspelling of the English name of a Pokemon that's not even in the game) to Ivysaur. I know most people understand the list (though I've seen loads of questions asking what "Zako" means), but I can't be the only person who is bugged by Venasaur.