Took me a while to figure this one out...
To add a button to the Outlook explorer context menu you need to get the "Context Menu" CommandBar.
This command bar instance is only created when the user right clicks in the explorer so in order to know when such a bar is
created you have to listen to the OnUpdate event of the Explorer's CommandBars collection.
Inside the OnUpdate event handler you can check if the context menu CommandBar exist :
CommandBar bar = ActiveExplorer.CommandBars["Context Menu"];
After getting the conext menu CommandBar you need to change it's Protection property to allow customization, add your button, and change the Protection back.
That's it... enjoy :)