Indexing is only responsible for increased processor usage (seen in the Activity Monitor as "mds" and "mdworker" processes taking up almost 90% of the processing power), not necesssarily for the shutdown.
You can test it very easily by opening MacintoshHD/Library/Logs/DiagnosticReports and find the most recent *.ShutdownSTALL files. Identify the troubled applications, open the activity monitor and force quit their processes then try to shutdown. You'll see it'll take only a few seconds after you do that.
If the shutdown is indeed back to normal, you'll have to make sure those applications are up-to-date or removed from your system. In my case there were several, but the last one was HP IO Trap Monitor, and I had to manually remove it from MacintoshHD/Library/StartupItems, otherwise it would always run on startup and cause "shutdownSTALL", proven by the log generated in the above mentioned folder.
I agree, you do NOT have to reinstall. And I say this because I did reinstall last Sunday and the results were quite interesting:
Re: Slower startup with Lion