How would I restore Spotlight search to my menu bar? (10.7)
I would imagine that inverting your commands would do the trick. Try:

sudo mdutil -a -i on
sudo chmod 755 /System/Library/CoreServices/Search.bundle/Contents/MacOS/Search
sudo killall SystemUIServer