Here in the UK I do consider this to be junk mail, and I do throw it away, but I agree with you that its a little bit scary, because they know my details, and enough to make a call about my worthiness.
In fact - when I moved to the UK, several years ago, I found it difficult to get a credit card (understandably) and it was this 'junk mail' that prompted me to go to MY bank and apply for one - which was then granted.
It was scary how they knew I'm eligible before I did, or before my own bank thought of offering me a card.
Here in the UK, I don't think they are allowed to do anything that would affect the credit score, as they ought to warn you first if they did, but from my experience above they certainly don't just randomly send it to people.
I think the pre-approval thing is only partially true, I'm sure they still do the 'real' check if and when you apply.