Cloudflare will not reply to requests for unknown hostnames. This is exactly the same behaviour as any such service. (If you just point a load of random MX records at Microsoft do you expect them to know your intent without any configuration being performed in their systems?
The ways to make a hostname “known” to Cloudflare are:
Adding the domain as a full setup.
Adding the hostname using a CNAME setup.
Using Cloudflare for SAAS (as stated by @sdayman above).
Using Custom Hostnames (essentially the same as SAAS)