Spotlight's Privacy tab not backed up by Time Machine?
Default Time Machine exclusions are in the file /System/Library/CoreServices/backupd.bundle/Contents/Resources/StdExclusions.plist

In 10.7.5 this file has a section named:
PathsExcluded
Which contains:
/.Spotlight-V100

So it is very likely that /.Spotlight-V100/Store-V1/Exclusions.plist will not be backed up by Time Machine.

I don't know where the "Spotlight Privacy tab" preferences are stored.