I have the same problem and none of the solutions here fixed my problem. I had installed some game from extras-devel and this added about 9000 pictures to my gallery.... i removed the game but now i have 9000 broken thumbnail images in my gallery and the lag is so huge it makes gallery completely useless. And everytime the indexer starts running it almost freezes the phone and runs for 7 to 15 minutes. the only way to make the phone usable again is to kill hildon-thumbnailerd wich is aggressivly thumbnailing non-exsisting pictures (thumbing its own ***)...
Have anyone come up with a working solution yet?