>If the user has already signed up, send them a helpful "hey, you've already signed up" message in their inbox.

Well put. Im also a fan of 'If this wasn't you, click here' link within the email to more positively ID the request as malicious