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.