Searching for files / folders on Server

Bit of a strange problem this one but I hope someone out there will have a solution for it? We are having problems searching for Files or Folders on the server we use. This is only occuring on the newer Mac's we have 10.4 the user says they are able to search the local disk fine but when they try searching for anything on the server nothing happens. Apparently they are using Finder and Spotlight but both don't work!!

The server is a Windows Server (2003) but as I said the older Mac's we have are able to search the folders no problem (using Sherlock 2).

Sorry if some of the terminology is not correct but I am very new to the Mac world but our department have been given the task of supporting all Mac's now!!!

Any help would be appreciated as I am losing the will to live now!!!!

Do you know hao the Macs are connecting to the W2K3 server? You might try installing Services for Mac on the server or connecting via a different protocol.

As far as I know they are connecting via TCP/IP we have got File and Print Services for Mac installed on the Win 2003 server.

How do you actually authenticate,..SMB, Appletalk, etc?