With the following patch things work as expected:

(ldap-search "(uid=<uid>)"
               "ldap://<host>"
               '("mail")
               nil
               t)
=> ((("dn" "cn=<NAME>,L=<REGION>,DC=<DOMAIN>,DC=COM") ("mail" 
"<name>@<domain>.com")))

I tried to make the patch as conservative as possible and intentionally 
do not check syntax of the dn line if its parsing is not required.