I second the concern other monks have raised: if you use secured emails (signed and/or encrypted) in your environment, you will need to be VERY careful not to break those messages. Altering only the Subject header is much safer, and I recommend only appending a parenthetical "(EXTERNAL ORIGIN)" there.

You could also (probably) alter the display name in the From header to insert "(EXTERNAL ORIGIN)" similarly, but see the other monks' concerns that users will learn to ignore the warning.

If you are really this paranoid, the best solution is to set up a parallel internal-only email system such that each user will have two inboxes: one that receives mail globally and one that only receives internal mail. Most modern clients can easily handle multiple accounts.