The only example I can come up with is in Mario Kart Double Dash!! I think it changes when all things are unlocked to a bit darker and more serious background.

But generally I like the concept of changing menu with progress in the game. Small changes that happen fairly often so that the change is subtle but noticeable when looking. Being able to see what one has accomplished so far directly at the menu can probably fuel my motivation to keep going.

Not quite on topic, but I always thought Mario Sunshine had a cool feature, the world got brighter as the player collected Shines.

I believe Yoshi's Island does this - the background of the main menu changes depends on far through the game you are. I think the background reflects what world you're on on the file you most recently played.

Yep. It is a reason to keep playing, I remember with detroit wanting to know what the AI will say next and heading to the main menu after every choice or story beat but I suppose Detroit is an extreme example of this feature. 

Yeah, Detroit was cool because when starting the game you never knew what the AI lady would say. And when she asked to be set free and leave, it blew my mind for a moment. Of course I let her go, but I kinda missed her after that :D

Same lol. Oddly, she holds up with the best characters in the game.

Pokémon stadium on N64 replaces its entire screen after the first round.

Yeah RPGs do this with the main menu. Marvel Ultimate Alliance 3 title screen changes depending on what chapter you are on. Spiderman 2 does it. Mario Kart games do it. But title screen only. That's fairly common I thought. When you beat Stellar Blade, Eve is wearing something from the end of the game on the title screen. Astral Chain after beating the game the character no longer appears on the main title screen.