How about algorithmically sequestering suspicious tweets? Reclaiming a tweet and making it live again would involve something like captcha and would have to be done by the person who made the original "false" tweet.

That way you are doing the scalable stuff. And you have crowd-sourced (back to the original tweeter) the burden of identifying what is real.