I distinctly remember people being a bit unnerved when I'd call them back and say "Hey, I saw you called...". My girlfriend at the time was particularly disturbed that I'd know she called even when she didn't leave a message. People were used to treating unanswered calls as if they never happened, and felt a bit violated when you knew that they had been investing effort into contacting you instead of making a casual "what's up?" call.
It's very strange to think about such attitudes in the context of modern communication. :)