Lion not searching SMB volume
I was able to get this working by adding the volume to Privacy section of Spotlight System Preferences, then removing said share from the same location.

I think this is how I got it working in previous versions as well.