Time Machine: Indexing backup......yawn....FIXED

Yeah it's getting boring seeing that message (and/or 'Waiting for index to be ready' in system logs /var/log/system.log) when your Mac is supposed to be actually backing up. I had this problem on Snow Leopard and then for a while on Lion but I now seem to have sorted it. I tried a few approaches and removing the spotlight index actually fixed it this time (though other times it has just been a question of waiting):

• Wait: It can take a loooong time to complete backups and indexing of backups so wait a few hours or even a day or so to see if it just sorts itself out.
• Repair Backup:
1. Turn off Time Machine in the preferences.
2. Mount the Time Machine Backups as follows: In Finder you navigate to your backup disk and then find your machine's actual backup file (your_computer_name.sparsebundle) and double click on it - it will put a new disk in Finder's sidebar: 'Time Machine Backups'. 
3. Then open up Disk Utility and select the 'Time Machine Backups' disk and click repair.
4. Eject the 'Time Machine Backups' disk and re-enable Time Machine in the system prefs.
• Remove Spotlight Index: Follow steps (1) and (2) above then open a Terminal window and type the following:

  sudo rm -rf /Volumes/Time\ Machine\ Backups/.Spotlight-V100

  
  Then follow step (4) above. After this your backups may take longer for a day or so whilst Time Machine rebuilds its indexes but it should settle down soon.
• Disable Spotlight for TM Backups: Spotlight can be disabled by firstly ensuring that 'Time Machine Backups' is
  mounted (see (2) above). The going to Spotlight Prefs and adding the disk to the 'Privacy' section. Alternatively it can be done on the command line as follows:

  sudo mdutil -i off /Volumes/Time\ Machine\ Backups

If you don't get anywhere with these approaches then check out this guy's page which has plenty of other things to try.

[Updated: 26oct12: Cleanup and Pondini link]