I have an iMac Late 2006 with Lion installed. I don't know since when, but since 3-4 weeks ago I am having this problem.
The point is, every time I restart my iMac or boot it, Spotlight starts to reindex again.
I already test to disable Spotlight, remove /.Spotlight-V100 and enable Spotlight again but it didn't solve it. I don't know how to debug/detect the problem but it is so bad, because it impacts on iMac performance...
I don't know if it is important, but I also have installed Windows 7 on Bootcamp. However it is marked as non-indexing volume on Spotlight's Preferences. I also tried to repair permissions, but it didn't work.