Entire Directory search

When adding a printer users search Entire Directory, sometimes its takes ages and no printers are displayed. If browse is then used to select the actual domain then printers will be displayed.
Does anyone know why this could be and how to sort it?