Certainly, the spotlight daemon should be killed during shutdown like every other daemon, so that shouldn't be an issue.
You may want to try booting in "verbose" mode (cmd+v during poweron). That also does a verbose shutdown, which may provide you with clues as to what's failing or hanging during the shutdown process.
Can't see what encryption would have to do with it.
Note that Jason Snell (
http://www.sixcolors.com) had a very similar sounding problem that ended up being caused by Adobe Creative Cloud...