Your description and the log you posted disagree: is the problem with email coming into your box (what you said) or email leaving your box (what the log says)?
And I'd like to know you're persisting with sendmail, since you've essentially said you can't or won't change.
Wade.