Got some feedback from our Network Manager.
From our tests, Cloudflare is working properly. Here is a test from a CPT location to MyBB (hosted on Cloudlfare):
cpt ~]$ traceroute -q 1 -w 1 mybroadband.co.za
traceroute to mybroadband.co.za (104.20.10.169), 30 hops max, 60 byte packets
1 cpt-os2.ip.adsl.co.za (169.1.2.249) 0.754 ms
2 169-1-21-83.ip.afrihost.co.za (169.1.21.83) 0.086 ms
3 cloudflare.ixp.capetown (196.10.140.198) 0.128 ms
4 104.20.10.169 (104.20.10.169) 0.100 ms
So this means that any differences could be due to how Cloudflare sees us, but we peer at NAP Africa, so this should not be an issue. It's more likely that Cloudflare may choose to make some services only available in JHB, and routes all traffic there. Some IP's we tested were only available in JHB, so that is the most likely reason.