Cross domain Business Rules, who has got ideas?

We are moving away from a single application landscape towards a more distributed service oriented landscape. This has impact on the way we have to deal with Data Integrity. In the 'old days' we were confined to one dataset, in which we could check our data integrity by means of simple programming with triggers and constraints, or the addition of a Business Rule Engine which is bound to the datamodel. The only discussion we had was about the place where rules were checked (in the screen or in the database).
I am currently doing (nice) work for a company where they are moving away from their ‘single application’ back-offices (one being USoft, a Dutch company which used to be known as the Business Rule company) towards a Service Oriented environment. The landscape is going to be separated in domains, based upon ownership of the different functionalities.
Business Rule thinking is part of my clients DNA, so we really have to define a thorough solution when validating rules across domains.
The rules of engagement are
-Domains are independent
-Transactions executed in one system may not be hindered by restrictions defined in another system
-Business rules are defined and owned by the domains. These rules can be used across domains, but are always started by the domain who owns the rule.

How do we deal with cross domain Business Rules?
Consider for instance two domains, Relation and Education. Within the Education domain we have a business rule 'An active education can only be connected to an active relation'. It is the responsibility of the Education domain to uphold this rule. When the relation is de-activated within the Relation domain, this is allowed, since the Relation domain is not responsible for the Education domain. So at this point in time we have an invalid situation.
How to deal with this?
We could agree that the Relation domain sends information about the de-activation to a central messaging mechanism where other domains can subscribe for these type of messages (i.e. the Education domain). The Education domain is then responsible for taking actions in order to create a valid situation. This could be the closing of the Education belonging to the Relation. Part of the Governance of the Education domain is then that periodically should be checked if open educations exist which belong to closed relations. This to be sure that invalid situations have occurred and the subscription mechanism did not work right.
The ease of checking our Business Rules and uphold the data integrity in a single application environment is gone in the distributed service oriented world. Who has got experiences/ideas how to deal with the cross domain validation problem?