You can usually just hit the DNS for the domain, and if it doesn't respond you can assume it's not taken. You might hit a couple of domains that are registered with no NS set, but they are few and far between. I've used a similar process before and been able to check hundreds of domains a second.
In your case you could probably do a DNS check, display "probably available", and in the background do the time consuming WHOIS scrape.