Surely one of the potential solutions has to be verifying accounts with a formal ID (even if you choose to keep the public facing part anonymous)? Then give users the ability to hide(/block? "You can't @ this person if you are not verified") everything from accounts that haven't been verified?
It wouldn't solve all the problems, but would surely go some way? And you still have the ability to live in a Twitter wild-west if you want to.