Search Fails

We rebuild some machines at our site from Windows NT to win 2K, when we log the domain users to the domain on their workstations we select start > search to continue with rebuild, search fails and we loose all icons and taskbar on the screen, we areforced to do ctrl-alt delete to log off and assign the users power user rights on the local machine in oreder to use the search for files and folders. Is their a policy on the domain that does this or a policy on the local workstation?????