I had a similar problem that showed up a few days ago. Strangely enough, none of the solutions worked from this thread-- and some other common solutions (starting/stopping the WDM with net stop uxsms) failed as well.
I went to change the theme, and then the problem disappeared. Changing back brought the problem back. So, having the taskbar always on top somehow became a setting in that specific theme.
Lesson: If none of the other solutions work, try changing the theme.
It seems that 'taskbar always on top', though no longer an option, can still manifest itself in the desktop settings. I'm going to try to track it down in the registry.