If you're using XP, try this: right-click on taskbar, click Properties, check Hide Inactive Icons box then click Customize, highlight proper icon (with left-click) and change behavior to "always show".
Do what he said (the box is unchecked by default, but I'm not sure).
Then, do this: Go to the Control Panel and click Power Options. After that, click the Advanced tab and click the check box for "Always show icon on the taskbar". Click Apply then OK at the bottom, not Cancel. It should stay on when you restart.
Also, what kind of anti-virus software do you have? Do you have a program that wipes your hard drive clean after every reboot? Do you have something that blocks new programs from being added to startup?