Didn't happen to me, but a friend can't find one of his AONE6 long-haul flight coupons-- the one he is due to use next, so maybe an agent pulled it by accident.

It's on AA stock, AA ticket #, missing coupon is for AA EZE-JFK. Originally issued by a TA in AKL.

Any experience with what can be done in such a case?

Contact the TA is the obvious answer

On your behalf or mine? Because the TA was contacted, of course, and was not able to help.

I'm looking more for advice from someone who's actually gone through the procedure with the airline that is required in a case like this-- I've been told there is $100 fee and paperwork, etc. Can it be done at a CTO? AIrport? Need notary? Etc.

I had this happen on a round trip ticket (agent did pull 2 flight coupons on the previous flight, the airline actually found it as part of the lost ticket processing). I had to file the form and pay the fee for a lost ticket (this was available from the airline ticket counter) and my original ticket was re-issued. As I had to travel the day that I discovered the missing coupon, I had to buy a replacement ticket. This was then refunded (even though it had been used) when I got the lost ticket re-issued and then returned it. Apparently you can't exchange or refund a lost ticket, so it was a rather cumbersome process and took 90 days.
But for a OWE ticket can't you just re-issue it and forget that there is a lost segment coupon? This is cheaper than the lost ticket fee and much easier to do. For a re-issue I've never seen them actually look at the remaining coupons, all that counts is that the new reissue is within the rules and the base ticket stock (ticket number) matches (I think).

I've lost count of the number of times I've reissued my owe's but in the situtations I can remember I've noticed that agents tend to go through every coupon remaining in the original ticket - often double checking the number of coupons after removing them from the ticket. Personally I would not risk trying this strategy as the agent could rightly assume that the coupons were used out of sequence - potentially voiding the ticket as a whole.