Thank you both, it works! 
DamienDLSkinSolution: Thank you! I thought that something severe could be wrong with my site. I now guess this is not the case and I am using the solution you suggested. The absolute links seem to work fine in all of the e-mail clients I have tested. 
LissaE: I'd tried to figure out how Zen Cart built the e-mails from the templates, but, I'd looked over the line:
HTML Code:
<base href="$BASE_HREF" />
I edited the functions_email.php file to print out:
PHP Code:
$block['BASE_HREF']
It was correctly printing the location of my catalog. I then checked the e-mail in the admin by printing out:
At the bottom of the function zen_build_html_email_from_template(). The source is being correctly generated.
Thank you for pointing out the <base> tag to me. I was previously confused by how Zen Cart built the e-mails.
I now guess the problem is with some e-mail clients, possibly just webmail clients (I was using hotmail) and not Zen Cart or my website. I think that having a second <head> defined in the e-mail itself might cause the base header to be incorrectly set by hotmail. I found this old post: http://www.vbulletin.com/forum/showt...ag-and-Hotmail
Has anybody been able to see their logo in html e-mails to hotmail without the absolute link modification suggested by DamienDLSkinSolution and LJ Global? 
Thank you both again!
-- EDIT --
Just to clarify LissaE...
In email/email_template_direct_email.html etc... the source reads:
HTML Code:
<head>
<base href="$BASE_HREF" />
</head>
<body>
<img alt="logo" src="email/header.jpg" />
</body>
However, when I view the source using firebug in hotmail (after receiving the e-mail) the source is magically:
HTML Code:
<img alt="logo" src="http://email/header.jpg" />
I am guessing this is Microsoft's doing.
-- EDIT --