app/bundle ID is the primary identifier on the backend. Any app name associated with it, is fluid. Best way to find out if a name is taken is to add an app and see if you can get beyond that meta data iTC step. Tip: If you like a name, and it's not already used, grab it...don't wait.
The reason you can't find a given name in the store is that someone has 'staged' an app with that name, meaning they've already used the name, but not yet gone as far as the store. Used to be a time limit on how long you could sit on a name before it was yanked back in the pool, but as usual, devs found a way, and manage to still hang onto ones they like.
Not a new practice, some wonder if certain names are squatted on like domains. Darker hearts accuse some squatters of grabbing names they never intend to use, in an effort to harass competitors. Branding, as always, is king...dilly, dilly.