O câmbio é péssimo nisso. O software de correio do Linux é gratuito. Instale-o em uma caixa, configure um subdomínio para todos os e-mails específicos do seu aplicativo que você enviar. (Como myapp.mycompany.tld, então todos os seus e-mails vêm de [email protected])
Seria bastante fácil escrever (ou pedir a alguém para escrever) um aplicativo rápido e sujo que receberia e processaria as mensagens devolvidas e notificaria seu aplicativo usando algo como SOAP.
Se você é um ambiente somente para Windows, não adianta fugir para executar um servidor Linux único, mas não conheço uma maneira de fazer isso com o Exchange.
Outra opção pode ser incorporar uma string única de caracteres no cabeçalho, assunto ou corpo de cada mensagem. Use X-MyApp-Id: blah. Claro que isso pode atrapalhar mais filtros de spam ...