Working on an issue with directory assistance this morning - an admin had created a new directory database to support external users and added it to the existing DA.nsf. While testing the database, the test external users couldn't login - got an invalid password error everytime. Reviewing the configurations, everything looked fine.
I got involved and enabled debug_directory_assistance=1 and debug_namelookup=1 and started testing. The debug output revealed that the search wasn't hitting the new directory database, even though a “show xdir” showed it was there and further checking revealed it was configured as expected.
Then I went to look at the design and found out something interesting. There were duplicate views and forms in the database, and the database was using a “newer” design than the server. After replacing the design of the database and rebuilding the views, the users were able to login successfully.
There is a technote that describes this situation as well, though it refers to Domino 7, guess it isn't just that release ;). The important thing to look for is two “Directory Assistance” views visible in the view navigator. If you see this, you'll want to replace the design.