A way out could be to make a separate tree (or an entirely separate database) where you store the dn and the uid, and since you control that database, you can give access to it by anonymous, to find the dn, and then bind to the 'real' database with the found dn and the password. Obviously, keeping the second database in sync with the main database will be a pain. It could be done, but it seems there are various obstacles in your way.
--Quanah
-- Quanah Gibson-Mount Principal Software Developer ITSS/TSS/Computing Systems ITSS/TSS/Infrastructure Operations Stanford University GnuPG Public Key: http://www.stanford.edu/~quanah/pgp.html