Contract data search and storage, how can this scale?

I’m writing a contract were a user inputs a string code and gets an NFT in return. The string should only work once, meaning I need to store it so that I can check if it was used before.

I’m having difficulty understanding how Ethereum can scale when something like this could rapidly become extremely gas expensive, increasing for each subsequent user (as the data keeps increasing, thus requiring more resources to be checked). A few million entries would mean each node having to do a resource intensive job, for something extremely basic, that is searching for a match, every time the contract is used.

I understand how this will consume lots of Gas and the costs being passed to the user, yet the data remains there even if not used, and from the programming side there isn’t much that can be done to avoid it, even when what we are trying to achieve is so basic for any other type of computing platform.

Are there any special ways for me to check if something already happened on a contract, that will keep gas down? Perhaps I’m missing something.

Thank you for any replies.