Although it's expensive in server processing, you could do a server side sort (if your LDAP server supports the control):

LDAP::Control::Sort

to get the highest uid, then ++ it.