How to generate random values without duplication when collision is likely and expensive?

I know there are a lot of questions like this, but they all seem different in one key respect: my collision management problem is more challenging.

My sample space is sequences of the form aaaaa, where a is letter [a-z]. So that's 26^5 = 11,881,376 combinations. (Note that I have a fairly small word size (5) and alphabet size (26). This is because I need reasonably memorable words. This means that I might have to assign around one million of the 12 million total possibiliites, which means that collision would be far more likely than, say, choosing 100 integers out of 2^32 possible ones.)

Also, I need to generate a random value and it must not collide with any existing values, but these existing values are generated over a long period of time and stored in a database. In other words, I don't have them in memory for an easy collision check.

Most algorithms for generating a random value without duplication involve generating a value and just testing it for a collision, and repeating until there is no collision. But here that test would mean a database call, which would be much more expensive, and my collision rate is much higher. So I think I will have problems.

Is there a better way to do this?