If you only do it for one window or don't close that window last
it would be preserved by the setting of the last window.
In case you have some hidden windows check to see that
iexplore.exe is gone from the Task Manager list of processes
to know that your preferences are really being saved.
Merely closing all the apparent IE windows and then trying to check
your preference by reopening one would only confirm that the last
IE window was closed without the Search bar present. I.e., a hidden
or unnoticed IE window could still be present with that setting and
when finally closed by shutdown its setting would be the one preserved.
Another possibility is that there is something in your Startup programs
doing this. That falls into the realm of malware which you can find
*frequent* suggestions for dealing with, including the ultimate action
of using the tomcoyote HijackThis! tool and submitting its results
to a spyware forum for analysis.
Good luck
Robert Aldwinckle