The problem seems to be that in some cases, UA believes that it's received confirmation, and generates a new receipt, but it fails to communicate the correct e-ticket number to the partner. Keep in mind that there are multiple steps involved:

1. UA requests space from OZ, which creates a record in the OZ system
2. OZ confirms space available to UA and updates the record in their system accordingly
3. UA creates e-ticket and emails customer
4. UA transmits e-ticket number to OZ to link to the record in OZ's system and to ensure that OZ can get paid

If steps 1-3 succeed, but step 4 fails, OZ will see a record in its system that's linked to an invalid ticket. Based on forum reports, it seems that some airlines periodically clean up reservations in this state by deleting them.

Now, if OP had a valid UA e-ticket that covered the OZ flights, the OZ rep could have created a record manually, forced inventory, and applied the ticket number from UA. The fact that the OZ rep asked OP to get UA to reissue the ticket, and that UA tried and failed, suggests that might not have been the case -- that it likely failed in step 2.

Incidentally, you can get seat assignments without a ticket -- that's how UA allows you to select seats during the ticketing process, for example. Even on partner airlines, the record can have seat assignments even though it doesn't have a ticket attached -- it's actually common for seats to be assigned during the reservation process as soon as one airline creates a record in a foreign reservation system.

PS: 72 hour confirmation is the IATA rule, but Star Alliance requires a response within 24 hours.