MacOS – Spotlight’s Privacy tab not backed up by Time Machine

To answer your first question about the keychain and whether you should encrypt backups: the passwords in your keychain are already encrypted, that's why you always have to type a password (by default your login password) to show stored passwords. So there's no immediate need to encrypt.

Of course, you could add Time Machine encryption to provide a further layer of security. This is possible starting with OS X Lion and Mountain Lion (from http://support.apple.com/kb/ht1427):

OS X Lion and Mountain Lion let you encrypt the Time Machine backup external drive using FileVault 2.

FileVault2 also uses your login password, though. So if the bad guys are able to guess or crack that password, they will have also access to your keychain information. Choosing different passwords for login and for accessing your keychain would protect the keychain passwords in such an event.

Either way, use strong passwords, password quality is of foremost importance to protect your data.

EDIT:

The OP asked in a comment how to set different passwords for login and keychain. Here is how:

• Open Utilities>Keychain Access.

• Right click each keychain and select 'Change Password for Keychain XYZ':

  

If you prefer to use your current password as keychain password and change your login password, log in using another account and change your account's password from System Preferences>Users & Groups. That will only change your login password, not your keychain password.

Try rebuild index

From the Apple () menu, choose System Preferences.
Click Spotlight.
Click the Privacy tab.
Drag a folder or an entire volume (your hard drive) to the list.
If prompted for confirmation, click OK.
Remove the item or volume you just added to the list by clicking
it and then clicking the minus ("-") button.
Close Spotlight preferences.
Spotlight will re-index the contents of the folder or volume.

You can also use the command line to rebuild Spotlight’s index.
Open the Terminal application and enter the following command:

sudo mdutil -E /

Authenticate with your administrator password,
and a message appears indicating that the index will be rebuilt.
Spotlight rebuilds the index of your hard disk.
You can track the rebuilding progress by clicking the Spotlight menu.