External SMTP or Exchange Mail Server
To me it sounds as if they are running their own Exchange mail server and want your Plesk server to 'forward' their domain's email to their external Exchange server. Please verify this with the client. SBS is Small Business Server and can be setup as an Exchange server.
If so, then once you have their IP address for the Exchange server, you need to reconfigure your Plesk and Qmail so that the domain's mail is disabled in Plesk, then do the following to the Qmail control files (this is one solution which works for us, but may not be the 'only' way):
/var/qmail/control/virtualdomains
-remove the domain from this file
-this will tell Qmail that the domain's email is not local
/var/qmail/control/smtproutes
-create or edit the file, add the client domain, IP address, port number on a single line, each item separated by colons ":" with no spaces.
-this will tell Qmail where to 'forward' the domain's email to
/var/qmail/control/rcpthosts
-this file gets rewritten by Plesk, so make sure their domain is NOT listed in this file, but make sure it IS put into a file called /var/qmail/control/morercpthosts
/var/qmail/control/morercpthosts
-this file does not exist by default, so you'll need to create it
-put the domain name into this file
-this will tell Qmail to accept email for the domain (from other domains hosted on your server)
-this file does NOT get rewritten by Plesk
Putting the DNS entries (mail.domain.com, or as panaman posted smtp.domain.com, pop.domain.com) should still be done so that the MX records for the domain are still resolvable to the proper IP address. You should make A record(s) which point to the IP (mail.domain.com. A ip.add.re.ss), then make sure the MX records point to that, it should already. We try to avoid using CNAMES whenever possible.
Normally the 'mail.domain.com' is already an A record pointing to the IP on your Plesk server, so you just have to delete that one and create a new one with the new IP. But I don't want to 'assume' anything about your DNS template or how the domain's DNS is currently setup now...