I really love
Melissa, it's got such a sweet, delicate sound to it. Plus my best friend in primary school was named Mellisa, and although I don't like that spelling, the sound of the name is special to me.
I could probably personally get past the 80s-trendy thing, but I'm not sure if it'd fly with the rest of my family.
Nicknames would have to be
Missy or Lissy though, I dislike
Mel.
Melanie doesn't appeal to me - I don't like 'ee'-sound endings very much, and
Melanie really is too 80s-trendy. It also has no nn alternatives to
Mel.