I just read Steve Griffin's excellent post on store providers under Outlook 2003 (Read it here.) As luck would have it, I just happened to be investigating an issue with a third-party MAPI provider and Outlook 2003's shortcut bar. The problem reported was that if you created a shortcut to a folder in the third-party MAPI store on the Outlook 2003 Shortcut bar, it would disappear the next time you started Outlook. Guess what the problem was...go on...guess.
Yep..PR_RECORD_KEY. As it turns out, Outlook 2003 relies on PR_RECORD_KEY to make these shortcuts work. This provider did not expose this property in their tables, though they did expose them on the underlying objects themselves (messages and folders). To be more precise, if you included PR_RECORD_KEY in your SPropTagArray passed into SetColumns on a contents table or hierarchy table, you wouldn't get an error, but the values would all be set to MAPI_E_NOT_FOUND, rather than the actual values from the objects in the table!
Because Outlook couldn't get PR_RECORD_KEY in the hierarchy table when it started looking for the target folder, it removed the shortcut, assuming it was invalid.
So, the key “take-away” of this post and Steve's post is that if you are writing a MAPI store provider, you should make sure your PR_RECORD_KEY implementation is solid. Besides this shortcut problem (and Steve's nothing rendering problem), I've also seen crashes resulting from deficient or missing PR_RECORD_KEY implementations.