Не уверен, что поможет, но можно попробвать в /etc/mail/access прописать одни IP адреса с призаком RELAY, а другие - DENY. Может, DENY все равно пропустит локальные адреса.
Можно, была точно такая же проблема, написал соответствующие правила и все ок (уже около полгода работают, проблем не замечал). Если надо могу выслать : me@spirit.org.ua или emailme@ukr.net