After some research, your question made me realize that I had the same problem in my mail server, so first of all, thanx.
Second, you should note that, by default, postfix blocks this kind of traffic. In the manual smtpd_reject_unlisted_recipient:
smtpd_reject_unlisted_recipient (default: yes)
Request that the Postfix SMTP server rejects mail for unknown recipient addresses, even when no explicit reject_unlisted_recipient access restriction is specified. This prevents the Postfix queue from filling up with undeliverable MAILER-DAEMON messages.
So, why are you getting 250 OK for unknown destination mails? Because of these lines:
mydestination = $myhostname, localhost.$mydomain, localhost
virtual_alias_maps = hash:/etc/postfix/virtual
The smtpd_reject_unlisted_recipient checks destination mails but very specifically:
An address is always considered "known" when it matches a virtual(5) alias or a canonical(5) mapping.
The recipient domain matches $mydestination, $inet_interfaces or $proxy_interfaces, but the recipient is not listed in $local_recipient_maps, and $local_recipient_maps is not null.
The recipient domain matches $virtual_alias_domains but the recipient is not listed in $virtual_alias_maps.
The recipient domain matches $virtual_mailbox_domains but the recipient is not listed in $virtual_mailbox_maps, and $virtual_mailbox_maps is not null.
The recipient domain matches $relay_domains but the recipient is not listed in $relay_recipient_maps, and $relay_recipient_maps is not null.
As your mydestination does not include your $mydomain (only the servername and localhost) and you do not have any *_domains in place, there are no other checks for "known" destinations.
You only need to add:
virtual_alias_domains = $mydomain
an reload postfix. (If I'm getting your config right and all your mail are in the form "user@domain.com")
If that does not work, you might try this:
smtpd_recipient_restrictions = permit_mynetworks, reject_unauth_destination, reject_unverified_recipient
NOTE: it will check via RCPT TO command if the destination trully exists for both incoming and outgoing messages. Use with caution since it makes an extra connection for each new destination and will take some time to respond to every mail your server processes (It can take a few seconds to test each destination).
Best Answer
If it isn't flagged as spam, but alice rejects the mail, I can't see a way for your Postfix server to not bounce the mail back to the victim, without turning off NDR's :(
Perhaps if alice marked that mail as spam somewhere in the header back to you?