I wish i had a solution but sadly have exactly the same problem. I restored to default, then checked registry entries. But then this happened.. Just now (as i was writing this..!), i got a crash log message from my VMWare workstation, which is interesting because it wasn't running, and haven't run that for days and there have been several restarts since then. Then Windows Explorer told me it has stopped working. I opened a new Win/explorer, and pass the beer & peanuts i have my columns back! To recap what i know i did.. in the forum page about how to set Windows Explorer to default, it shows how to downloaded a registry file and merge it with my existing one. I did that. I then opened the registry to also do the second method and confirmed that the registry entries that you are supposed to delete were already gone. (good). Then i restarted and collapsed in tears when i saw that my column headers bar was still gone and so can't change column width. Then the strange business above happened which led to the columns restoring. I hope this helps someone.
[Additional note: The column headers have disappeared again so i am no closer to having a solution. It is even worse. When i tried a third party folder viewer, (JExplorer) it also has the same problems, it looks like it uses a lot of the installed Windows explorer code which normally makes sense but in this case is bad news for me.] I will radiate intensely good thoughts in the general direction of anyone who can suggest a fix for this! ! ]