First of all, many MTAs provide a sendmail binary for sending mail. So it doesn't have to be actual SendMail.

Secondly, if the machine can contact a working Internet-aware DNS and has a default route out through your firewall - i.e. you could browse the 'net from it - then most any MTA can be dropped in and it will automatically find the right host and delivery mail a-okay. There might be a wrinkle if SMTP outbound is not permitted. In that case, you should drop your Exchange admins a line and ask about letting it forward SMTP for you. Then you don't need a working DNS, either.

Wade.