I did not create this solution, but it is what we have implemented for a similar purpose and it is very easy and effective.
The basic idea is to have an objectClass of 'uidNext', which has one required attribute of uidNumber. To begin, you create an entry with this objectClass and your desired starting uidNumber.
You would check the uidNumber attribute of uidNext, delete the entry, then recreate the uidNext entry with uidNumber+1. Use the original uidNumber for your new user.
Read more about the implementation: