Right you can mix the domain-based approach with a route-based approach on the other side and still have it work. Keep in mind the only real difference between domain-based and route-based VPNs is how traffic is determined to be "interesting" (to borrow a Cisco term) and requires encryption vs. just being sent in the clear. Once established the VPN protocols more or less operate the same regardless of which one you are using.
However the traffic selector determination is also impacted (called Proxy-IDs/subnets in IKEv1 Phase 2), with a route-based VPN normally you utilize what Check Point calls a "universal tunnel" (dual 0.0.0.0/0's) whereas with domain-based individual subnets are negotiated. This is controlled from the VPN Tunnel Sharing screen of the VPN Community, do you have it set to "one tunnel per gateway"?
With the introduction of per-VPN Community VPN domains in R80.40, that code was definitely touched and may be the cause of your issue. You will need to take a closer look at the selectors being proposed with vpn debug ikeon and ikeview. Any chance the R80.40 changes are causing many more IPSec SAs to be negotiated than before and you are hitting some kind of limit on SAs that can simultaneously exist on the peer? I remember reading an SK about this but can't find it right now.
Whether a peer configured for route-based VPNs will accept a non-universal tunnel (i.e. a subset of it) is highly dependent on the other side's vendor type and configuration.
Gateway Performance Optimization R81.20 Course
now available at maxpowerfirewalls.com