For complicated reasons, sometimes a registered domain will show up as available. This should only happen in less than 1% of cases and I'm working on reducing it to zero.
As others have stated, it seems to be much more than 1%... and it absolutely must be zero if the service is to have any credibility.
Anyone can make a list of words: that's the trivial part. What you are "selling" (even if for free) is the capability to verify availability fast; you need to deliver on that promise for the whole thing to have any value.
I'd say the value is even negative when registered domains are shown as available, because then it's wasting users' time.
(Sorry to be blunt but I don't know how else to put it).
Maybe you count as "available", domains for which the .com is taken but other gTLDs are not?
Personally when I search for a domain I'm only interested in .com, but maybe you could let users choose what TLDs they care about?