I don't have a lot of experience with this, but hope to in the future.
For a few weeks we had our iMac connected to our NT network via DAVE. It worked very well. Sherlock indexed the NT volumes it was connected to during indexing. I don't remember using Sherlock to search for files on the NT servers, however.
If your NT or Win2000 volumes are set up for Mac file sharing, they should fully support Sherlock indexing. Using DAVE was important for us because we could not expect support from our IS staff to enable Mac file sharing.
Hope this helps. Let us know how it comes out.