When printing out specific emails, they either print with the email headers
(the from, to, subject) or without. I have selected File - Print or
hitting the print icon directly. Even played with the settings inside the
print setup.

I am using Outlook 2003 with Exchange 2003 in the backend.

Any ideas?