Excel 2007 and 2010 can save multicolumn sort order criteria - but only for tables

The sort order amnesia of Excel 2007 was one of the odder regressions in the history of Microsoft Office. After decades of remembering the last set of sort criteria, Excel forgot them.

Sometimes, if you had a data range with headers and no gaps, and if you clicked on a header in the table, the sort order seemed to stay with the header.

Maybe.

Apparently this is true for Excel 2010. Microsoft documents this (emphases mine):

Sort criteria are saved with the workbook so that you can reapply the sort each time that you open the workbook for an Excel table, but not for a range of cells. If you want to save sort criteria so that you can periodically reapply a sort when you open a workbook, then it's a good idea to use a table. This is especially important for multicolumn sorts or for sorts that take a long time to create.

Tables are more special in 2007 than in prior versions of Excel. I found a description of how to do this in an otherwise obscure forum (maybe a splog?) by dFrank:

Why Excel 2007 doesn't save ... Data -> Sort ... settings?: 

It is amazing, but why such a simple question take ages to resolve? 

Why Microsoft didn't put a huge warning label that SORT ORDER in EXCEL 2007 is now behaves completely different from previous versions. 

For years now, I was under impression that is it just a bug, and nothing can be done about it. 

Finally, some super-small font on some supper-obscure web site whispers that you only can save sort on a table, but on on a range. 

What the h*** is a table. A table is LIST in previous Excel versions. Never heard of it. But we do not need to know about this. Let's just go thorgh the steps:
-01- Select a range of cells just a bunch of columns and convert it to table (Ctrl T);
-02- Remove annoying unneeded table formatting (Design --> Table Style --> Clear);
-03- Remove filters (Data - Filter);
-04- Apply a sort. 

Next time you are in the file, your sort is finally preserved.

In my limited testing I don't think you need to remove data filters, they are compatible with tables.