How to change mail server's domain name?

Question

Domain is delegated to the Plesk DNS:
1. Navigate to Domains > example.com > DNS Settings;
2. Click on MX record;
3. Set Mail exchange server to the desired domain.
Domain is not delegated to the Plesk DNS:
1. Find authoritative DNS provider for the domain:
  
  # dig +short example.com NS
  ns2.he.net.
  ns5.he.net.
  ns4.he.net.
  ns3.he.net.
  ns1.he.net.
2. Navigate to the DNS provider's web-interface and login;
3. Set MX record to the desired domain.
  
  Note: For more information on how to work with DNS on domain registrar's side refer to the similar article: How to configure name server for domain on registrar's side?