I have dealt with this since the days of xp. I have friends that auto-hide the taskbar so they get more space for their U.O. gaming window. The only solutions that I found that works 100% is, do not auto-hide the taskbar. I know that is not the answer you want to hear, but after 9+ years of dealing with it, and no solution other than no auto-hide, it is a sad reality.
There is one other option, format and fresh install and pray that the taskbar auto-hide issue does not return. But it likely will if you continue to use auto-hide.
I will say this much more, on the xp machines, this was only present after .net framework was installed.
I will keep looking back to this thread in the future, because I personally would like to know how to resolve the problem as well.