Limiting new accounts to, say, 20 per day per IP should severely mitigate most attacks, especially the ones not specifically targetted at your site. For the targeted ones, deal with them as they come up, in a more or less manual way. You don't want to have 10000 new fake account creations per second but you don't need to bother your legitimate users with overly annoying measures like Captcha.