That's right.
Perhaps the person who wrote the documentation you read meant to say that the certificate needs to cover the server's hostname as configured in the mail client rather than the domain used for e-mail addresses. For instance, the user might receive e-mails at username@ourhostname.co.za but if the server name that the user enters in the mail client is darwin.irhost.co.za, the certificate should cover darwin.irhost.co.za rather than ourhostname.co.za. This distinction should be drawn in effectively the opposite direction from the way you interpreted it, but it's still possible to describe it as "the cert should be the server's host name" (as opposed to the name after the @ in the end-user's e-mail address).
You could still offer this, but in order to do so you would have to issue certificates for these names yourself. You can actually do that, if you want, after the CNAME is in place because Let's Encrypt will allow you to issue certificate for names for which you are the target of a CNAME. For instance, if the customer does pop.clientname.co.za IN CNAME popourhostname.co.za (or if you control the DNS and do this yourself), then you can issue a Let's Encrypt certificate for pop.clientname.co.za using a private key that you control! That certificate would then be accepted by the e-mail clients for a connection to pop.clientname.co.za.
If this is a common configuration for you, it should be possible for you to script this so that it gets set up automatically—assuming that you don't mind the comparatively large number of certificate issuances. Since they relate to separate customer domains, it shouldn't create a problem for the Let's Encrypt rate limits.
I know this distinction might seem somewhat arbitrary to you, but it's effectively based on the idea that CNAMEs encountered in DNS are "believed" at certificate issuance time, but not at certificate verification time. That distinction is a little bit arbitrary but it sort of stems from an intuition that certificate authorities are better-equipped to detect and avoid DNS attacks than, for example, a user's mobile device connecting to a service from an Internet café. For various reasons the certificate authority "gets to" trust DNS more than the certificate verifier does, and therefore if you want the CNAME to be trusted in this process, you have to issue certificates referring to that name.