Frequently there will be MX records or something similar pointing directly to the server. Even error pages can potentially leak a direct, unprotected IP.

There are two ways to bypass CloudFlare and related services. 1) Most of the time, as Kephael said, websites expose their back end IPs through subdomains like ssh.domain.com or ftp.domain.com. MX records also sometimes function in the same way. There are a variety of ways to resolve a domain through CloudFlare. 2) CloudFlare bypass scripts can be bought for around $400 which manipulate the JavaScript per client when sending an attack (mainly by disabling JavaScript). This prevents the so called "challenge pages" from blocking malicious traffic, effectively slipping through CloudFlare protection. Most of these scripts work on most other providers such as Sucuri as well.

Here's how it could be done:

Spin up a hefty AWS instance and connect to every single IPv4 IP while sending a HTTP get request on successful connects with a Host matching that of the domain. There are only 4 billion IPs. Look for successful code 200's with the same headers and content as the original website. Easier said than done though.

Btw, this attack can be prevented if you run a drop-all firewall and only whitelist the IPs listed here: https://www.cloudflare.com/ips/