In the "good old days" applicaitons would often un-hide the Taskbar so their notification icons could show an updated status and they could ensure it would be seen. I think this method has fallen out of favor, but older applications that haven't been updated could still be sending the commands to the system to show the Taskbar. Is it possible that you have an older app in the notification area that's affecting the Taskbar as described?
What notification area icons do you have (and what versions)?
For what it's worth, I just tried disabling Avast Pro 5.0 and it still allowed the Taskbar to auto-hide.
-Noel