My wife and I flew to Australia on Qantas in business class about a year ago -- I on a paid ticket and she on a FF award.

We were told that we got the last award seat on both of our trans-Pacific flights, which baffled me, since the business class cabin was virtually EMPTY on the outbound trip.

I just think they're being especially stingy. My strategy would be to just book the flights on two separate days, get the tickets, and sort out the scheduling later. That works for us probably 95 out of 100 times (not all on Qantas, of course).