If persistent visualization of relationships is important, you can try treating it like a sangkey diagram.
Sankey diagrams visualize the magnitude of flow between nodes in a network.
Here's a quick example (this one has magnitude and hover focus, but there's lots more things you can do):
What you have now looks like 3 disparate lists. It sounds like what you're trying to do is visualize relationships.
Your original attempt at using different colors for different relationships will break down, both from visual noise, and inability to distinguish color relationships for entities that have multiple connections.
If you want to have edges (visible connection lines) that show many to many relationships, you can use the sangkey without showing the order of magnitude (unless there's a magnitude factor that's important to highlight).
D3.js has many good examples. The main thing is that keeping the edges visible at all times means that the nodes show the relationships without any manipulation. You'll see this used in Google Analytics behavior flow, but D3 has many more examples.
Focusing on a particular entity and its ancestors (or descendents):
If you want to drill down on a specific relationship, you can select a canonical starting point, and highlight that node. The relationships can be highlighted from that starting point, both bottom up or top down.
To unselect you can have a button on hover (or visible) that can deselect the node, or selecting another node changes the relationship. I'm not sure, but it's a starting point.
You said the requirement needs to have multiselect, but I suspect that's because the current grids will show no relationships at a glance. The sangkey will keep that relationship visible, and you might be still able to do multiselect by 'focusing' on one or more nodes at the same list level, similar to what I have below.
You can also experiment with graying down the unselected nodes, so it's very clear.
download bmml source – Wireframes created with Balsamiq Mockups