Spotlight reports "Indexing and searching disabled" in Lion
I had the exact same problem, with all solutions above failing identically. Then I reexamined the directory listing for / and found a hidden file .metadata_never_index in the root directory. I removed this file and was able to turn spotlight on again with 
mdutil -i on /.

mds is now reindexing the hard disk, all looks good for now.