If you have been subject to any sort of CAsA audit on you medical in the past DO THE FAA MEDICAL IN AUSTRALIA. If you're a straightforward case, do it in the States (it will be cheaper).
Believe it or not, yes, it's true, FAA are a PITA if your medical is subject to special issue, it will take longer than CAsA to settle and the tests they ask for are more stringent than CAsA.
The 'HR' departments of regional airlines are a bit of a joke, they won't tell you what needs to be in place prior to INDOC (well, some don't). It ain't no fun forking out for accomodation, unpaid while waiting for the medical or any other requirement.