Wow! It worked! We still use 95 at work and I just tried it. The start key on the keyboard won't bring it back either... that's just nuts. Is there a way to get it back without restarting explorer?

You used to be able to close the Start button in base Win95. Just click on it, press ESC (leaving the focus on it). Then press Alt+Hyphen to bring up the Start button's system menu.