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.
If you can figure out how to do the request on the client side, that would mitigate the issue.
Otherwise, I'd say you're probably out of luck. (You could try doing the query over IPv6, but eventually they'll just block the entire subnet, so I don't know if it's worth the trouble.)
Not quit the same (a username might be reserved internally), but either way, nobody else can use the name.