I have found that if I do File, Send to, Recipient Using a Fax Modem and go through that Wizard inside of Word 2003, I get a valid fax ever time.

So what is it about a regular Ctrl P that is causing me this problem?