Anthony,
You are correct that unconditional mutual redistribution would create some undesirable routing behavior.
If the mutual redistribution is conditional then you'll be fine. For the example environment perhaps the scheme below would work.
It's important that OSPF routes learned from BGP are not allowed to be advertised back into BGP. In order to prevent this give the OSPF routes learned from BGP a unique tag number at redistribution. A route-map used in OSPF to BGP redistribution will prevent those tagged routes from being re-advertised to BGP.
The service provider router (PE) will announce the opposing data center prefixes and these will get redistributed into OSPF as external routes. In this case this is not a problem as the OSPF internal route will always be preferred over an external route.
This scheme will allow the enterprise WAN routers (CE) to announce both data centers prefixes. In order to ensure predicable traffic pathing the BGP attribute AS-Path should be adjusted so each data center receives traffic destined to it directly. Create a prefix-list containing the opposing data center prefixes and increase the AS-Path as the routes are advertised to the PE. This will cause these routes to look unattractive in the MPLS cloud.
If your service provider will accept BGP communities set by you the customer; then there is more flexibility to this.
###################
route-map BGP2OSPF permit 10
set tag 999
exit
route-map OSPF2BGP deny 10
match tag 999
exit
route-map OSPF2BGP permit 20
# This pefix-list should contain all subnets
# from opposing data center
ip prefix-list OtherDataCenter 192.168.1.0/24
route-map OSCAR permit 10
match ip address prefix-list OtherDataCenter
set as-path prepend 3599 3599
exit
router ospf 10
redistribute bgp 3599 subnets route-map BGP2OSPF
exit
router bgp 3599
redistribute ospf 10 match internal external 1 external 2 route-map OSPF2BGP
neigbor 11.11.11.11 route-map OSCAR out
exit
Chris
