I just recently worked through an issue where messages in a custom message store would not sort on the Subject field.  Other text properties sorted fine, just not Subject.

The problem was because Outlook doesn't sort the Subject field on PR_SUBJECT.  It actually uses PR_NORMALIZED_SUBJECT, which should filter out any prefixes from the subject (like RE:, FWD:, etc).  So the problem boiled down to the store provider not supplying PR_NORMALIZED_SUBJECT in its contents tables.

It seemed fairly straightforward.  However, when I loaded the provider with MFCMapi, I saw that PR_NORMALIZED_SUBJECT wasn't in the table by default, but if I did a SetColumns on the table to add it, it showed up fine.  So what gives?

It turns out that Outlook is assuming that the message store provider will support sorting on a property that is not in the current column set on the table.  The provider did not add PR_NORMALIZED_SUBJECT to the underlying data in the table when it first created it, but it would add it dynamically to the table if it was explicitly asked for in a SetColumns.  So if Outlook had include PR_NORMALIZED_SUBJECT in its call to SetColumns, this would have worked.

At first I thought this was a problem with Outlook, but after reading MSDN documentation and Inside MAPI, I realized that it isn't.  A store can choose not to support sorting on properties that aren't in the current column set (by returning MAPI_E_TOO_COMPLEX) but this store did not.  Outlook may have still not retried the sort anyway though.

The solution here was to include PR_NORMALIZED_SUBJECT in the data used to create the table.  The provider was using MAPI's implementation of IMAPITable instead of implementing their own, and MAPI's implementation does support sorting on a property that is not in the current column set as long as that property is present in the underlying data.