[ahtihn]

It's impossible actually. Company names aren't unique. There is no global registry of company names. Even trademarks aren't globally unique.

[econ]

You start with the largest, work you way down then start work on local registers.

City names is probably enough but you can still allow ads from two the same businesses in the same city.

With domains it is even more obvious. No need to pretend everyone could be the nyt.com