"woher kommen Sie" and "wo kommen Sie her" can be interchanged, they are both polite questions about the wherefrom of a person.

Of course there are other contexts and slighty different wordings on the basis of the two.
"Wo kommst Du /kommen Sie denn her?" matches your "where (on earth) did you come from" and can be the exclamation of a mother at the sight of her dirty child, or it can be a puzzled question among any age, e.ge. when you expected the other person to show up from a different direction. Also, there you are also right, it can be the startled shout "where have you just sprung from?".
"Wo kommen Sie (jetzt) her": can be a boss who expected you at your desk, but you are returning from a place unknown to him.

I am sure, other folks will come up with more usages.

You're right for your first interpretation: no stress means I just want to know.

You can put a (slight) stress on "her".
It means
- "What is your point of departure?"

You can put the stress on SIE, in addition I'd expect an additional "denn" in a phrase like "Wo kommen SIE denn her?"
It means:
- "Why are you here? What are you doing here?" and
- "I wouldn't have expected you coming from there".

You can put a stress on "Wo", starting in a high pitch and ending even higher, making it an astonished question.
It means
- "What? Where did you come from? How extremely unsual / surprising!"