If your domain is pointed with CNAME using Cloudflare, yes you must configure the MX records from Cloudflare. (Cloudflare cPanel > DNS > Add MX records)
You could use a Zoho or ImprovMX for email handling
You’ll have to contact them and ask to clear your domain from their database, however I don’t know how could you do that, as they do not provide a contact e-mail address, nor a support forum.
But please note that ImprovMX only forwards e-mails sent to *@yourdomain.com to the specifid e-mail address. If you need more advanced services, please consider using Zoho.
Another good alternative would probably be Google.
Please follow this tutorial to set up MX records with Google Mail Service
If MX services say they can’t verify your domain, it might be due to Cloudflare’s security. Please go to your domain registrar, temporarily switch to registrar’s NSs, and then try again.