Darwin could be taken easily enough in mid-42 if the Japanese are willing to forgo some other operation (the Indian Ocean Raid probably being the most sensible to scrap). Because of how far away it is from literally anything else (there's a road to Alice Springs, but AS is still basically nowhere), it might as well be treated as an island. The Japanese had 25k men in Timor from about March. Use them.
Brisbane... won't go well. First, Japan has to take Port Moresby. No ifs, buts or maybes, they have to. Else there will be an ungodly amount of Allied subs picking off every tanker, cargo ship, transport and anything else that sails through the Coral Sea. Moresby isn't likely to fall based on the OTL attack in May, but there's enough of a chance that it can.
Next, we've got to consider Cairns, Townsville, Cooktown and other potential bases in northern Queensland. But the Allied plan was always to retreat to the "Brisbane Line", so I'll just wave those away for now. New Caledonia, on the other side, I won't. From about April 42, NC is going to be defended by the AmeriCal division, one of the best in the US Army. Something like 25k men, all well trained, well supplied (Noumea harbour was literally overflowing with supply ships at times!), probably have fairly good air support. At the same time, the Japanese have to run EVERYTHING out of Truk or Rabaul. That's a few thousand km, close to the limit of the IJN's range (for fuel if nothing else!). It can be reached, but the IJN will only be able to hang around for a couple of days. Then it is a month round-trip to refuel. That means whatever troops the Japanese land are only going to have air cover ("support" is being generous) for about one day in every ten, which will have to come off carriers (even if the Japanese take the New Hebrides, a Zero won't be able to achieve much more than flying in, fighting for like 5 minutes, and then having to go back. And I doubt Japan even had the fuel to spare to resupply Efate repeatedly. If you scrap Midway, the Japanese have enough fuel to use about a third of the IJN near-constantly until the end of the year. Then they run out entirely.
OK, so we handwave the fall of Moresby, neutralise far north QLD and the Heer Logistics Fairy finds a way to make New Caledonia work. Now what?
Well, there's something like a quarter million Allied troops on the Brisbane line by now. Australia has enough locally grown food to feed them forever (it's not like NC or another island where everything has to be shipped in). Australia has an arms industry, so at least some of their equipment will be fine (we were building tanks at one point, so rifles won't be a problem).
Japan's problem is NOT manpower. They had something like 100k on New Britain at one point and another 100k on New Guinea (IIRC that was 1943, but the troops are still somewhere - doesn't really matter). The problem is getting that manpower to the front, and supplying it once there. At Guadalcanal, the Japanese force topped out at about 30k, and Brisbane (or NC for that matter) is a lot further than Guadalcanal from wherever these troops are being supplied from (Rabaul isn't making these supplies either). My most generous estimate is that Japan could probably run 10k troops at a time to wherever they want them to go in this theatre (Midway had 5k in the invasion force, and anyone who brings up the Philippines or DEI needs reminding that those are a lot closer to Japan than Rabaul is!).
So Japan might be able to drip-feed sets of 10k men to Australia once a month. Probably less than that in successive waves as they'll need to bring more rice, ammo &c each time (even on Guadalcanal the troops weren't getting enough, and Brisbane is going to be worse!). Even Douglas MacArthur can defeat a force 1/25th of his force's size if given a month to do so.
Even the IJA thought invading Australia was such a terrible plan that they just "nope"d out of it. When those madmen think something is impossible, you can be absolutely sure that it will never work. I didn't even bring in the US Navy, but they won't make things any easier either!
If you're interested, I did write a timeline about what I think to be a sort of "best case" for Japan in the South Pacific - link is in my sig.
- BNC