1) As I remember, the Indexing service does not work in the way you think it works. Indexing is a local drive situation: only the local drives on a machine are indexed. So, running Indexing service on a server will not help clients attaching to theserver via Shared Folders. (now, Indexing will work with IIS and web pages, and that is the only method I can think of when it helps remote clients; unfortunately, that is not your situation here). So, running Indexing on the server won't help the clients, and the clients own Indexing service (if they are 2KPro/XP clients) won't index a mapped drive.
So, this brings me to
2) Are you sure the logged on users have Read and List Folder Contents rights to the mapped drives? Check out the user permissions on the Shared folder (verify the Shared folder permissions and the NTFS Security permissions) to make sure users have enough rights to do a search.
hope this helps