Retry method for generating unique code

In an app, a user can generate a six-digit alphanumeric code. The code needs to be checked against a remote database (via Web API) to ensure it is unique. In my tests, collisions occurred on average only one in ~24K times with a high of 85K and a low of 170. It is the latter that concerns me. Although the table is emptied of expired codes daily, at some point there will be a collision. Although unlikely, it could happen with very few records in the table.

A simplistic solution would be to keep running the generation/check until a unique code is created. In all likelihood, this would only mean 1-2 iterations. But there's no guarantee. And certainly it can't run unfettered.

The next step would be to put a limit - say 5 tries - through a simple loop. This may be enough of a solution. Despite concern that the user would be frustrated if it ultimately fails, if it does there's probably enough wrong with the overall system to ruin the user experience anyway.

I have good exponential backoff code so although this is not a network issue (also a concern), it may help to incorporate it into the retry scheme. In fact, that might be a nice catch-all solution. Given 5 increasing temporal delays in retrying, it would allow both enough chances for the logical code to exceed the chances of a collision and mitigate introducing more stress on network resources.

Any suggestions/observations would be appreciated.