Sorry, I did the example in Word 2010 which does allow rotation and then saved it in Word 2003 format.

Just make your text box the size you want your header in your margin. Paste the text for the header into it. Select the text. Use the Tables and borders text rotation button to rotate it.