jkovar,
The solution I used for this was to create an email_header.gif (or whatever name you want) in each store's templates/[template_name]/images folder.

Then in the includes/config_sites/[site config file] include this line:
define('EMAIL_HEADER_IMAGE','includes/templates/'. $template_dir. '/images/email_header.gif');