My LIST view has columns--I just selected a file at random, changed it to LIST view and the column headers were Name, Album artist, Date modified, and Size.
I don't have "deep freeze" installed (I don't even know what that is.)
List view: (note that it has no columns)
Details view:
Now, if I understand your original post correctly- Windows Explorer <is> saving the view setting (details, with columns) but it isn't saving the columns you have selected.
If you want to have a number of folders with customized columns, you're probably out of luck-the storage mechanism only stores 128 folder views (sounds like more then it is) and if you revisit a folder whose settings have been purged it will appear using the defaults. (these settings are stored in the keys Allan just posted, I believe, as well as in hidden desktop.ini files in each folder)
Personally, I set all my defaults to the Details view (folder options, View tab, "Apply to all folders" When in details View). The columns save position and size, and have not changed as far as I've noticed, and I use explorer heavily for managing folders and files.
I'd give the bagMRUsize entry a change, as Allan suggested. You'll have to reset your options yet again, but with any luck they will be persistent.
Another possibility is some sort of conflict between different explorer instances if you have "use a separate process for each folder window" option.