Your setup is a good solution, ie a central server with indexing happening on the server. However, you just need to make sure that the server uses the same 'mapping' of the files that the clients will. For example:
Server: Shared files stored on a locally mounted 'G:' drive in the folder:
G:\Team\Shared\Documents
shared as 'Documents'
Client: Mapped network drive 'M:' maps to the Documents folder:
\\Server\Documents
For the Client to search the index properly the Server must use the SAME mapping as the client, so rather than indexing 'G:\Team\Shared\Documents' the Server should index 'M:'. More information is available here:
Help file: Shared Indexes
Note: If your server is not running Windows you can update the index using a separate Windows machine, the indexing may just take longer.