Over processed digitally altered sound of any kind become unnatural to human listeners because it's not what we are used to hearing in the real world. The sound will always be wrong because of the way our brains work.
Hit a bell and everyone will envision a bell. Record the bell and change the pitch a little bit and most will still say that's a bell. Change the pitch to much and people will go WTF is that?
So you need to fool peoples ears into thinking they are hearing what your intending them to hear by applying just the right amount and never too much. If you push the limits then other acoustical treatments like reverb might mask it, but even that will fail eventually.
Here in lies the danger of pitching tools like melodyne. They will work fine for small amounts of pitch change but things become strange beyond a certain point.
I find you can use digital harmony if it's back in the mix and a little more reverb than I would like. For in your face dry vocals nobody and no software can fool the human ear.
So what I sometimes do is try my best to sing that higher part as close as I can and then turd polish it with pitch correction. If I make a pitch mistake on a lead vocal, I re sing it,,, faster and much better results. I only use pitch correction on harmony and the odd client who keeps hittin the same wrong note.