CSet 5 was intended for use for your subscreen. Or at least I think that's what it was for, since the BS Tileset uses it for that.
There really isn't any big reason we couldn't have all the main CSets vary by palette. By this, I mean csets 0, 1, 2, 3, 4, 5, 7, 8, 9, 10, and 11. This would allow every enemy to change color if you wanted them to (although perhaps we might want this off by default since it would probably only confuse n00bs). This would incur an extra memory requirement, but not really that big of a one. Assuming the list above, that would mean csets 0, 1, 5, 7, 8, 10, and 11 would have to be added. That's 7 csets. Each cset has 16 entries, each 2 bytes. That's 224 bytes extra per palette. On the average quest, this would only add a couple KB to the storage space. Since quests take MB of space, this wouldn't be a big deal.
BTW, I would vote for keeping palette cycling and not overwriting it. While it isn't oft used anymore, it is useful for certain effects. Heat glow in a fire dungeon certainly comes to mind.
On a related note, I do recall that not too long ago we were discussing the fact that only 12 of the 16 csets are normally available (the other 4 can be placed using cset2 and actually do show up in the global cset editor). I recall doing some experiments and finding that 1 was for bosses, 1 was for the GUI, 1 was for the triforce flash, and 1 was for the faded effect that occurs when you open the main menu (i.e. everything goes gray). However, it appears that this is only done for a split second before this is replaced with the normal image with all the pallete entries modified to grays. Point is, it doesn't seem that this cset really does anything anymore, so this would be a candidate for some more color space. (I forget which cset this is, but its the one that is filled with grays in the cset editor. You can actually use it if I remember correctly via the cset2 trick, but you will get a brief flash of weird color whenever you hit escape)
If we really wanted more colors, the triforce flash cset could also be opened up if it were made to be handled in similar fashion to the menu graying.