Remember that a directory is a hierarchical name space; if you don't
take advantage of that fact then you may as well just use an RDBMS.
Telephone numbers are also a hierarchical name space; there's a natural
mapping that makes this problem simple:
Given a user with subscriber number xxx-yyyyy just split the number into
two components:
number=yyyyy,prefix=xxx,ou=subscribers,dc=example,dc=com
Make the application always transform its lookups to match this naming
scheme. Then, for users who are "local" to the system, you do a base
search on exactly their number. For 123-4567, lookup
number=4567,prefix=123,ou=subscribers,dc=example,dc=com
If it exists, you get the result back immediately. If the query is
999-12345 and only the prefix exists, then your lookup for
number=12345,prefix=999,ou=subscribers,dc=example,dc=com
will fail, and the result will come back with a matchedDN of
prefix=999,ou=subscribers,dc=example,dc=com
Then your app just has to look up the matchedDN entry, and proceed from
there. "Wildcards" are unnecessary.