Знаешь, у меня такая же ситуация только на Шлюзе стоит Postfix, и ты не поверишь, но все работает отлично. Твоя проблема в том, что ты переписывашь адрес получателя, не делай этого и тогда все заработает. Не знаю как в sendmail, а в Postfix это прописывается в "transport table". Удачи.