Never EVER click on links of which the URL does not begin with the official host of the company the mail is from (or claims to be).
And by URL I mean the actual link, not the stuff you'll see in the mail itself.
The only way to see the true URL is by looking at your statusbar in your email client (or browser). What is displayed in the text can be whatever they wanted it to be...
eg: look at this link. Nothing suspicious right? Take a look again and this time hoover your mouse over the link and look at your status bar.
http://www.msgplus.net/
So, this is a very important reason why you should always have status bar visible (may sound stupid but I know many people who fail to see the use of them... well here you go
)!
-------
Thus I'm very sure that this
https://www.paypal.com/cgi-bin/webscr/?cmd=_login-run-secure link was the think you saw in the mail, but what was the actual URL? I very highly doubt it was that same link...
-------
Also, email addresses themself say absolutely nothing. Except that official sites will always use offcial emails, but then again, so will sites and people who want to steal from you..
/ 
