Yep, thats pretty much how it works at the moment (see https://github.com/trevorah/usernique/blob/master/server.js). The issue is that the server is sending out quite a few of these hits to twitter, and twitter is smart enough to start reject requests when things get a bit too much.
I'm not a node guy, but I found this module for Whois checks - https://npmjs.org/package/whois-available
It uses the IANA Whois service, an admittedly cursory look doesn't turn up anything re: rate limits, but you could just do a get request on the root url and only check Whois if it 404s to be safe.
http://www.iana.org/whois
Whois wouldn't help here. The problem is that so many requests are going to twitter.com/[username] that they start sending false 404s (or some other error, not 200) because of rate limiting.