Postfix and compromised accounts

It sounds like backscatter (NDR spam) to me, rather than your server being an open relay. Exchange Server 2003 by default is not an open relay. You can check whether or not your Exchange server is an open relay by using any number of online tests. You can help prevent backscatter spam in a few ways:

1. Disable NDR's on your Exchange server.

2. Filter email sent to recipients that don't exist in AD.

EDIT

After reading the other answers and reading the comments to my answer, here's an updated answer:

1. Filter email sent to recipients that don't exist in AD. This is probably the more preferred method to deal with backscatter at your Exchange server.

2. Disable NDR's on your Exchange server. This is the least preferred method and was probably not the best suggestion on my part. While it does deal with the problem, it may not be completely in the spirit of RFC 5321 (although it probably is acceptable based on the verbage of RFC 5321 section 6.2).

What you want to do requires to treat mails from users using your server as their MSA (i.e. their outgoing relay) with a different policy than those received from 3rd parties (i.e. when your mailserver is acting in it's MX role). Fortunately, amavis has just the right tool for you: Policy Banks.

Let's see how you could define a policy for your users:

$policy_bank{'PREQ-SUB'} = {
        originating => 1, # indicates client is ours, allows signing
        final_spam_destiny => D_DISCARD, # discard spam
        final_virus_destiny => D_DISCARD, # discard spam
        warnspamsender => 1, # send a warning 
        forward_method => 'smtp:127.0.0.1:10025', # you probably need to adjust this
        smtpd_discard_ehlo_keywords => ['8BITMIME'], # force mail conversion to Q/P
        smtpd_greeting_banner => '${helo-name} ${protocol} ${product} SUBMISSION service ready',
        spam_admin_maps  => ["postmaster\@example.net"],  # warn of spam from us
        virus_admin_maps => ["postmaster\@example.net"],  # warn of viruses from us
};

From the naming of this policy bank, you can already guess that I'm running this as a pre-queue filter that get's triggered if mail is delivered via the submission TCP port 587. To make this configuration work, I told my Postfix MTA to deliver mails that the submission service received to localhost on port 10028 (whereas, when acting as public MX, the server forwards mail to port 10024). To activate two ports in amavis and bind the PREQ-SUB policy to port 10028, I'm using these settings:

# policy bank definition
$inet_socket_port = [10024, 10028];  # listen on listed inet tcp ports
$interface_policy{'10028'} = 'PREQ-SUB'; # mail submitted using TLS on submission/smtps port

The corresponding master.cf entry for Postfix is:

submission inet n - - - - smtpd -o smtpd_tls_security_level=encrypt 
  -o tls_preempt_cipherlist=$submission_tls_preempt_cipherlist 
  -o smtpd_tls_protocols=$submission_smtpd_tls_protocols 
  -o smtpd_tls_ciphers=$submission_smtpd_tls_ciphers 
  -o smtpd_tls_exclude_ciphers=$submission_smtpd_tls_exclude_ciphers 
  -o smtpd_sasl_auth_enable=yes 
  -o smtpd_recipient_restrictions=$submission_smtpd_recipient_restrictions 
  -o milter_macro_daemon_name=ORIGINATING 
  -o smtpd_proxy_filter=127.0.0.1:10028 
  -o syslog_name=postfix-submission/smtpd
  -o receive_override_options=no_header_body_checks

Note that this does actually do a bit more than simply send mails to amavis, e.g. set cipher lists and so on (you'll notice the main.cf variable references).

So, what can you do if your users do NOT submit their mail on port 587, or not all of them do? Well, you'll have to leave the land of 100% certainty then. amavis can analyze the contents of a mail and act on the presence of headers. One such headers could be the authenticated user's name which Postfix adds if you set smtpd_sasl_authenticated_header = yes. You could then tell amavis to act on this header:

package Amavis::Custom;
use strict;
BEGIN {
        import Amavis::Conf qw(:platform :confvars c cr ca $myhostname);
        import Amavis::Util qw(do_log untaint safe_encode safe_decode);
        import Amavis::rfc2821_2822_Tools;
        import Amavis::Notify qw(build_mime_entity);
}
sub new {
        my($class,$conn,$msginfo) = @_;
        my($self) = bless {}, $class;
        my $auth_sender = 0;
        foreach my $line (@{$msginfo->{'orig_header'}}) {
                $line =~ s/\n    / /g;
                # WARNING: you need to improve this to AT LEAST also match
                # for your OWN mail servers name!
                $auth_sender = 1 if $line =~ m/^Authenticated sender/i;
        }
        if ($auth_sender) {
                do_log(2, sprintf("Load pre-queue submission policy bank"));
                Amavis::load_policy_bank('PREQ-SUBMISSION')
        }
        return $self;
}
1;  # insure a defined return

Please don't ignore the warning within this code: Headers are easily fakeable, and other mail servers could insert an "Authenticated sender" header, too, so better match for something like "your-mailserver.example.net.*Authenticated sender".

On a final note, regarding one of your comments: Running a mail server DOES take a lot of time, and requires you to constantly monitor it for abuse. There is not "get out of jail free" card when it comes to taking part in the global email system!