@selecadm is generally correct, however I believe that Android ships its own root store, which should include the DST root certificate used for cross-signing by Let’s Encrypt.
My guess is that you are not sending the intermediate certificate along with your own certificate. This would result in clients not being able to build the trust chain to the trusted root certificate (unless it’s been cached from a previous request to a service that included the correct intermediate certificate).
How this is done depends on your mail server software. If you’re not using fullchain.pem or chain.pem anywhere in your configuration, you’re definitely looking at this problem. There have been a couple of threads for various mail servers here, maybe one of them has the information you need.