I'm not sure that the issue is so much Australian immigration as airline staff. They mayn't let him board just out of habit, even if he's waving a dozen work visas in their faces.

In these sorts of situations, what I usually do is buy a fully refundable return ticket. While they're not necessarily cheap, you can always get all your money back as long as you pick the right one and read the fine print.