The find fast issue is common to this problem. Another cause can be the way document paths and shortcuts are made by NT. By default shortcuts are mapped to a UNC path, rather than the drive listed in the shortcut target. For some reason, even though an appropriate drive mapping exists, the UNC creates a new one. This can be prevented at the server with server policies. I don't remember the exact path to the policy, but the policy turns off UNC mapping on shortcuts, and makes the shortcut targets absolute the the actual drive mapping. I have found this policy extremely useful for load balancing as well. I have moved entire directories to different servers/volumes with this policy in force. Without this policy active, the shortcuts would look for, and fail to find, the file in the old locations.
Good luck,