This is a design question really. There is no problem with the product. It actually functions correctly and your description suggests you well understand it.
You are correct, if you check against the user store then you will not find what is not there and so if too much time elapses between your check and your commitment then your calculated value may be taken and you won't be able to commit it anymore. You are correct that this is due to the multi thread and asynchronous nature of the product execution.
I say that this is a 'design' question since you will need to 'design' your solution taking into account the product's behavior and this exact possibility.
The way I see it , you have a few alternatives:
1. Perhaps the easiest would be: leave it as is. Mostly it won't happen. Chances of you processing users with similar enough first and last names almost at same time are probably minimal. This means you won't run into this often enough. What you can do is still monitor for this error, perhaps for this specific error maybe email the administrator with the failed ID, along with an explanation of this situation and ask they resubmit again. When they resubmit later this should be fine. You can also just gather all these failures and resubmit them automatically and only if failing the second time then you may want to alert your administrator.
2. You may change your code so that by the time it reserves a certain User ID then it will immediately create the user, then from there onward basically modify it (adding more attributes, roles, memberships, whatever).
3. You can also have your BLTH code manage its own 'registry' where the User IDs that passed the BLTH check will be written in some local file or some place where you will also check against that on top of the normal check which basically will ensure you're taking into account the User IDs that are 'under process' and 'being submitted' which are not yet known to your user store.
Honestly, I think solution #1 is probably the cleanest since you will allow your function to work in a clean way and simply resubmit your failures giving them another try as a second batch run , perhaps even a third. If all that fail then you may want to result to emails and manual intervention.
Hoping you found this helpful.
Regards,
Sagi