I think there are two approaches to this, the classical and the cryptographic way of doing this.
The classical method: In this method, you do the same as you would do on any computer. You store the list of minted names (in a UTxO). Given a new mint, the stateful minting policy would check that the new name is not in the list and makes sure the new state has it in its list. The problem with this design is that a blockchain is bound in transaction size. Currently, any transaction cannot exceed 16kb (more or less). So theoretically, the database cannot exceed this limit (note that this is the absolute upper bound, in practice it will be much lower).
Now you can also decide to shard the database captured by multiple UTxO's. For example, store all names that start with the letter "a" in one UTxO and the letters "b" in another. This method might work, since upon minting a new name, only the database of that letter is needed in a transaction. Now this is again limited since it might be the case that names that start with the letter "c" get minted a lot, rendering the database full at some point. So choosing a method how to shard is the key here, and this depends totally on your constraints on the name. But remember that this subdivision has to be deterministic, a validator should be able to decide if the appropriate database is used given a name!
The cryptographic method: Since space and time are bound on a blockchain, there are some clever ways to create bound algorithms that proof a statement. For example, using Merkle tree's you can prove that something is a member of a database in a relatively low-impact way. But these are involved from a dev perspective. Similarly, I found this paper that lets you prove that you correctly failed to prove membership of an element, effectively proving that it is not a member. The paper also has a nice non-interactive algorithm where a minting policy could probably act as the verifier. Note, however, that this paper leverage pairing curves, which won't be available until next HF (if we are optimistic!).
So to conclude, there are ways, but it depends on your specific application.