I would add
Margery and
Mallory to the short list of
Melody,
Melanie, and
Valerie. I agree with the pp that of the names you posted,
Valerie is the one readiest for a comeback. Something about the trendiness of V's, W's, and Z's make it a likely contender, whereas the M names now seem to be dominated by surnames--Madison, and then the endless Mac and Mc surnames.
I know one young woman named
Melody, maybe 20 yrs old, so born around 1990, and frankly, at the time that choice of name always struck me as so corny.
Natalie is a bit like
Valerie, too. Never super popular, yet more elegant than the diminutives from the same era with the i or y ending, names like
Patti and Susy.
Even if they are not currently in wide usage, any of these names seem intrinsically more tasteful than the current onslaught of surnames as first names.