Holy cow, I wrote a book!
Explorer does not set the auto-hide checkbox on its own.
Now, the taskbar does auto-hide even when the setting is unchecked
if it detects that the application is trying to go full-screen,
say, in order to show a slide show or
play World of Warcraft.
But that doesn't check the check-box.
Further investigation revealed that
the check-box was being checked programmatically
by one of the programs that the company used.
And it wasn't custom software but a commercial product
which targets the corporate market.
The customer reported back that the problem was sporadic.
They could not reproduce it consistently.
My guess is that the application in question was trying to
enable auto-hide temporarily for whatever reason.
At program startup, it checks the current auto-hide setting,
and if it's off, it programmatically turns auto-hide on.
previousState = IsAutoHideTaskbarEnabled();
When the program exits, it restores the original setting.
This is a highly fragile solution for several reasons:
What if the application crashes before it can restore the setting?
What if two people did this?
Oops, now we have a problem: Program B wants auto-hide on,
but Program A just turned it off.
Oops, the auto-hide setting was left in the 'on' state
after everybody thought they had restored it.
As a special case of What if two people did this?,
the Program B could be the Taskbar Properties page itself.
While your program is running, the user goes to Taskbar Properties
and sees that the checkbox is set incorrectly.
Maybe they go in and "fix it", and now Program A is running
with a visible taskbar.
What if the application tries to restore the state
after Explorer has already saved its settings?
When the user logs off, all processes are told to clean up their toys
and to go bed.
In response to WM_ENDSESSION,
Explorer saves out its settings and calls it a night.
What if this happens before the application programmatically unchecks
Explorer says, "Okay, I unchecked the box."
But Explorer already saved out its settings; these updated settings
aren't going to be saved again.
This is what happens when you expose a global setting programmatically.
People see the setting and think that twiddling it will solve their problem
looking for a local solution to their local problem,
in this case
creating a fullscreen window that covers the taskbar.