I never flew with AN until I started commuting between MEL and SYD on my way to/from my Asian base. (For some unaccountable reason I never wanted to travel with Australian ever again) Then it was every month, and family members too, as well as ID90 travel within Australia. My experience 100% of the time was that the AN service desk staff at MEL and SYD were just wonderful, all the time and always. Sometimes going waaaaay beyond the call of duty to get me a seat, even a jump seat with a "visiting" american pilot. The whole staff travel thing then, for me at least was so easy...in contrast to travelling with the Rat now, where inflexibility is the order of the day. Not at the level of the counter staff but in systems and rules.
I hope those handful of kind folks did find new jobs. I see one or two at QF desks now.