This network location can't be included because it is not indexed
In order for the Windows Search Service to be able to index a folder/share, the local SYSTEM account requires NTFS permissions on the server.
After setting these permissions, group policy was able to add the users' home shares to the Documents library and I was able to do this manually myself without the message, "This network location can't be included because it is not indexed."
Wouldn't it be nice if an error was logged in the System event log to let me know that Windows Search Service doesn't have the permissions it needs to index a folder?
One possible solution is to manually update registry keys which tell Windows where the "personal" folder is located.
[HKEY_CURRENT_USER\Software\Microsoft\Windows\CurrentVersion\Explorer\Shell Folders] "Personal"="\\\\server\\users\\username\\Documents"
[HKEY_CURRENT_USER\Software\Microsoft\Windows\CurrentVersion\Explorer\User Shell Folders] "Personal"="\\\\server\\users\\username\\Documents"
I believe these registry keys should be updated automatically when the group policy is applied.