Updated to reflect the updated question ...
These could all have the same meaning, which is "to feel the absence of," but you can also "miss someone" in the sense that you "miss" a target -- "to fail to hit the mark," which would suggest that you nearly did encounter the person but ultimately did not encounter them. You can also "miss someone" in the same way that you'd "miss" an appointment, by failing to attend. Not sure about the full etymology but you can miss a meeting (or a day of work) by just not getting out of bed. That is to say that you can be said to have missed an event that you made no effort to attend or that you didn't learn about until after the fact.
So "I always miss you" could mean that, like Mister Hooper and Snuffalufagus, you keep turning up just minutes after I've given up waiting for you.
Don't leave before 4:15! I will try to leave by 3 but but my boss keeps me late so I don't get the right bus and I always miss you.
Or it could mean that I never stop longing for you or I'm continually aware of your absence.
Hi honey, I'm home! Did you miss me? / I always miss you!
So this whole line could be saying
"I always arrive just after you've
left, so I don't get to see you, so I
long for you. I'm longing for you
or it could be saying
"I am always longing for you, which
causes me to be so distracted that I
don't arrive in time to see you, which
results in me longing for you more. I
very aware of your absence right now."
See also: https://secure.wikimedia.org/wiktionary/en/wiki/miss#Verb