Such a "not me" link only prevents abuse if the person receiving that email checks their email the instant it's sent and clicks the "not me" link instantly as well. Otherwise, someone could sign up for a site using a random person's email address and then do something malicious depending on the site/service... send emails/messages, post nasty forum messages, etc.

Granted, not all sites/services can be used for such maliciousness, but in those cases that the site can be used maliciously, a "not me" link is a corrective measure and not preventative measure.

Edit: zb put it more eloquently than I did.