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.
Best Answer
I "fixed" it forcing a new indexation but excluding the User directory. What happens? It is too slow, but has an end. Not is eternal. When it finish, you can add again your User directory and, after it finish, you can reboot safely without scare :)