Someone else has the problem here. We use 9i at work as well, and I'll double check version numbers to get you something more specific in terms of version numbers in 24 hours. But last I checked, when I tried it, it barfed that error at me.

Your first query is fine, as b is out joined to two tables a and a_outter_joined, but your second query is not, as it twice out joined to a. Well oracle can make the error message more clear, saying that "you either out joined two tables, or out joined the same table twice." ;-)

That problem has nothing to do with primary keys, foreign keys, or anything of the sort. That error has to do with how modern RDBMSes handle outer joins. Basically, it goes like this:
1. You construct your query.

    from A
    left outer join B on (a.foo = b.foo)
    left outer join C on (b.bar = c.bar)
   [download]

2. The query analyzer now tries to determine what order to join the tables to form the intermediate set that it will then limit on. (It's more complicated than that, but that's the basic idea.)
3. Let's say it tries to join B and C first. It does that, forming a set with all the items from B and items from C that match. Then it joins that to A. But, what items should be in C for those items in A that aren't in B? You run into the same problem if you join A to B first, then join that to C.

I guarantee that if you do this with all your tables having primary keys, that won't make a difference. If all your tables have foreign keys, then you're sidestepping the issue because the OUTER keyword won't mean anything.

Being right, does not endow the right to be rude; politeness costs nothing.
Being unknowing, is not the same as being stupid.
Expressing a contrary opinion, whether to the individual or the group, is more often a sign of deeper thought than of cantankerous belligerence.
Do not mistake your goals as the only goals; your opinion as the only opinion; your confidence as correctness. Saying you know better is not the same as explaining you know better.