"this network location can't be included because it is not indexed" on Windows 2008R2 Remote Desktop Services Hosting

I'm setting up a new terminal server for our users on Win2008R2 (I guess I should call it Remote Desktop Services now!)

When I try to change the location of "Documents" (by removing the default Documents library and adding a new one), to use the file server ie \\fileserver\username\Documents I get the message:

"This network location can't be included because it is not indexed"

I certainly don't want to make folders available offline, and in fact, I have set the GPO to prohibit offline folders on the terminal servers.

What is the best practice for document libraries on terminal server and network file shares?