After a little research, I see that many other people including a few who are working in domain environments are having this problem. Here are a few things I would like you to verify. Please check these in order and re-test after verifying each possibility:
#1 Windows Search1
Verify Windows Search is installed on the server hosting the user directories. Also, verify that Windows Search has fully indexed the users share on the server. Important note2 about installing Windows Search on the server - there is an Indexing Service and a Windows Search Service. Windows 7 clients will NOT work with the Indexing Service. Only one of those two service can be installed on the server at one time. If you installed the Indexing Service, please uninstall it and install the Windows Search Service.
#2 NTFS Permissions3
Verify the System account on the server has full permission of the users share and sub-directories. If the account does not have full permission for the users share, indexing may fail. If indexing fails, the documents location will not work correctly.
After you verify both of these, please remove the folder from the library on the computer you are having a problem with and then re-add that folder. Please post your results. Also, would you mind providing the Operating System you are running on the server?