Random thought: what if you gave users a unique code that they had to email back to the server to identify themselves.
The major issue I can see with it is that many people might like to use a email alias to signup (I prefer to use shabble+servicename@ for services which aren't too broken to accept a +) which isn't the same as their configured sender.
If they really want to service, they'll click the link.