I'm sure you've already thought of something along these lines, but I didn't see it mentioned. So...

I presume you have an easy way to know whether or not a given node has multiple parents? Assuming so, I have provided a "pivot" button in similar situations, one that takes the currently selected node and "reverses" the heirarchy, e.g. instead of showing the children, it shows the parents "belonging" to the child.

For example:

Books
  + Perl [ *Pivot* ]
  + Unix/Linux
  + SomethingElse
Reviews
Tech Sites
  + Perl 
  + Unix/Linux
  + SomethingElse
[download]

Becomes:

Perl
  + Books
  + Tech Sites
SomethingElse
Unix/Linux
[download]

Implementation tends to be fairly straightforward, if you're using a reasonably well-designed database/schema.

I've also found this to be a really interesting way to allow users to learn your heirarchy.

--f