First of all thanks Suhaib for the help :)
After more tests I think I now understand what happens.
Whenever the encrypted message gets written back to outlook's store (locally and on Exchange) THEN it's written back in plaintext. It gets written back when inserting Annotations or when moving it to a different folder programmatically.
And that is a severe security breach for me.
But interestingly, when I move the message directly within Outlook (ie with the UI as opposed to a macro) then it's NOT written back in plaintext. I think it's also true with the QuickSteps in Outlook 2010 but can't confirm at the moment.
So I guess then the question is more at the outlook/PGP interface level, or even maybe at the programmatic access to Outlook level: how to programatically move messages around outlook without storing the result in plaintext ? Is this even possible ?