This should not happen for .com names (where we do a live "double check"), but can happen with others. We build our index based on zone files and DNS, so if a name is not configured, it will show as available.
I had it happen for lots of .page, .dev, etc. Really cool utility though. :)