Root CauseThe troublesome CNAME is created automatically anytime you have your root A record marked as protected but have another record, usually a CNAME or MX, that references that is NOT protected. This is actually a very common situation, since by default CloudFlare will suggest an unprotected ssh CNAME record so you can use it for direct access. Please note that the CloudFlare interface doesn't give you any indication that the direct-connect record will be created for a given configuration, you can only determine its existence by looking it up with a tool such as dig or nslookup.
SolutionSimple, don't use a CNAME for any of your unprotected subdomains that references a protected record. Instead, make sure to use an A record. Yes, this means you will probably be updating more than one record if your origin server's IP has to change, but I think its a more than fair tradeoff. If you're using something like the modified ddclient or the CloudFlare API to set your IP then this is simple to automate for multiple records.
Further SuggestionsFor the most paranoid users, the even better solution is to not create any records that can be used to look up your origin server's IP at all. It's not any improvement if you got rid of the direct-connect record but still have an equally well known record like "ssh". If you MUST have a DNS entry that allows you to connect directly to the origin server at least try to make it uncommon, though this is of little help against DNS brute force enumeration tools.
An even more important task is proper firewall configuration for your origin server(s). Work under the assumption that your origin server's IP will be found and an attacker will try to bypass CloudFlare completely. Limit your publicly accessible ports to just what's essential. If all of your web traffic is supposed to pass through CloudFlare then there is most likely no reason to allow web traffic from anywhere else. CloudFlare's list of IP blocks can be found here (Note: these do change periodically as they add new locations).