It been in Explorer since Win 95.
Ctrl + X on the titlebar. It must be a file folder. Dialogs read this once per application (so you must stop and restart programs to see if it took).
Open Notepad, go File Open, set to all files (*.*) - look at the sort, close Notepad.
Open an Folder window (ie not a file open/save dialog - a normal folder window) via My Computer to C:\, sort how you want, Ctrl + X on title bar.
Open Notepad, go File Open - look at the sort, it changed.
Plus if you hold down control and click close while in a file folder it also updates
HKEY_CURRENT_USER\Software\Microsoft\Windows\CurrentVersion\Explorer
Shellstate=
This is mainly setting irrelevent things except it holds the global sort, which all the others override. But File Open dialog boxes only use this setting, so it basically only affects sorting in File Open dialogs. But it seems that sometimes an earlier windows versions setting get written here and other settings then aren't saved. It also stores show extensions, hide hidden files etc.
It seems this is a different structure (it got XP specific settings in it) to older OSs. Some non saving of settings is due to this key and I suspect a Win 95 structure gets written over the XP one.
If your sort doesn't change close Explorer (Start - Shutdown - Ctrl + Alt + Shift + click Close/Cancel), delete ShellState, and restart Explorer as the shell and try again. Shutting the shell down the way I describe saves settings.