The sneaky thing is their canned instructions say to dial
122 + billing code + 9 + 1 + area code + 7 digit phone number
which presumes that you are calling a US number. After some googling and trial and error, I succeeded in leaving a message on Rajeev's machine by doing
122 + billing code + 9 + 011 + 61 + 2 + [8 digits of local phone number]
with the semantics being, I think: I am billing a call to [billing code], it is an outside-of-CMU-call, it is an international call whose origin is the US, whose destination is Australia, specifically Central East Australia, and the local phone number is [8 digits of local phone number].
I feel kinda like I am keying in IP headers.
Oh, wow, those who don't look up their old livejournal entries first are doomed to repeat them. Except I think I have a few more hours of headstart now.