I am having the same issue in vista, I am sure it has only happened since installating SP1.
All my windows maximize over the taskbar. If I set to taskbar to be on top of other windows it works fine apart from when using media players in full screen (zoomplayer, powerdvd, mediaplayer classic) the taskbar stays there and doesnt disappear. Its quite annoying.
Is there any solution to get my windows to maximize to the taskbar and not over it?