I might have missed some of this thread.
Did anyone mention the solution given here?
http://www.rexconsulting.net/ldap-protocol-uidnumber.html
Store the next number to use in an objectclass in the directory, then
use atomic operations to increment it.
Would that help?