Sounds like a bug to me. Can you reproduce this with OpenLDAP 2.4.10?
No bug in search, at least. The uid attribute was not part of the entry until he explicitly added it with ldapmodify. Seems like he must have used slapadd to create the entries in the first place though, since ldapadd would not have created an entry without its RDN being present in the entry.
The entries were created with slapadd.
Regards, -- Josh Miller, RHCE