Stateful network intrusion detection, and even more so prevention, is a tough task in face of multiple upstream links. When traffic can flow in at one link and exit at another, a single monitor cannot reconstruct end-host state effectively. You can either accept this situation with all its implications (e.g., mediocre protection at best) or resort to a distributed solution that propagates state amongst the nodes.
Ideally you would push the monitors to the network edge , but it sounds like you have no control over the edge. Without detailed understanding of the network topology, this is a hard question to answer. For the remainder of this answer, I assume that you have at least the ability to deploy several monitors in your network to approximate the ideal of inspecting all upstream traffic.
The NIDS Cluster
The Bro network security monitor has a cluster mode, where a node can propagate state to other nodes. For example, when node A sees a FTP control connection, it may propagate this information to node B, so that it knows how to interpret the following high-port data connection. Another scenario where this comes in handy is distributed scan detection. If you have an infected machine in your network that performs outbound scans through multiple links, each node may keep a local counter and exchange it regularly with other nodes. For a more detailed analysis of state exchange, have a look at the NIDS cluster paper.
This cluster approach scales well do to the following insights:
The granularity of analysis and clustering is an entire connection. As long as you can ensure that packets belonging to the same connection end up at the same cluster node, you get good scalability. In single-upstream environments, a frontend typically slices the input traffic to achieve this constraint. In medium-sized networks, a Click router that rewrites MAC address often suffices, but larger environments often have to use dedicated high-performance devices. Our research group has very good experiences with cPacket CVU frontends, which can load-balance multi-10-Gbps links at line rate without dropping packets.
The size of the exchanged state is typically orders of magnitude smaller than the traffic a node observes. For example, if one nodes observes an big ISO image download, it will not propagate the very ISO image to other nodes, but for example just the name of the ISO image. Moreover, intra-connection analysis are already stateful, e.g, Bro follows the TCP state machine and exposes the HTTP message pipeline to the user.
Applying this to your scenario is a little more complicated, because you do not have a single upstream link. In order to scale well, you need to ensure that traffic from the same connection is inspected by the same node. In other words, the notion of a frontend is a little bit blurry because you have to manually route the packets to the corresponding cluster node. The exact overhead of this approach depends on your concrete topology.
 This does not preclude defense in depth. Adding more monitors at the core is a good idea as well, for example when no "roadwarrior" subnets are established to isolate mobile devices.