I want to fly from Sydney to Osaka (not necessarily KIX), leaving after business hours on Friday 1 September, or any time on subsequent days without eating into my holiday too much. There are no direct flights available, the cheapest nominal fare assuming no luggage is A$385 for JetStar (JQ952 & JQ15, which goes from Sydney to Cairns and then from Cairns to KIX), and the fastest scheduled flight is 12h 10m with ANA (ANA 880 & ANA 13). A flight this long is going to involve either an early departure, a late arrival, or trying to sleep in between.

I'm not fussed about how long I spend flying, but I want a reasonable trade-off between low price, and good "sleepability" - not having to wake up too early, not arriving too late in the evening, and ideally sleeping in a bed, but even trying to rest in an airplane seat is better than having to stay awake during a long layover at night or early in the morning.

Kayak gives me quite a few options, but none of them were perfect. The A$385 option from JetStar involves a 6am departure from Sydney to get to Cairns, and the next cheapest alternative at A$456 with Air Asia X (D7 221 & D7 536) has a four hour layover at 4am KUL time / 6am Sydney time, and A$467 with China Eastern (MU778 & MU747) has a 2h 20m layover at 5:30am KMG time / 6:30am Sydney time.

I was able to guess that there must be another way to get from Sydney to Cairns with Jetstar (or an allied airline). Flight JQ958 flies from Sydney to Cairns at a very pleasant time. According to Sleeping in Airports and Wikivoyage there's some youth hostels with free airport transfers, though I'll need to confirm they allow Aussies. The main disadvantage is that Jetstar charges for "extras" like meals and baggage, and it being a multi-leg trip may make it more expensive than a one-way trip.

However, listing this flight option in a search is difficult if not impossible. On Kayak, I tried biasing my search to find this option, and still couldn't find it. With this kayak search, I required that flights depart at 6:06 am or later (to ban 6am flights), I allowed it to "Show 573 longer flights", and that it stopover only in Cairns (JQ958 is a direct flight to Cairns, so the stopover shouldn't exclude this flight), and while it shows similar options when departing on other days, it doesn't show it (or any other flights) departing Sydney on Saturday 2 September.

Likewise on Ita matrix. Even on Jetstar's own website it wasn't shown if I searched for a one-way ticket, though it is apparently possible to book an unrelated one-way ticket that has lots of stopovers (flying via Melbourne, the Gold Coast and then Tokyo Narita). However, I could apparently create a multi-leg ticket that flew from Sydney to Cairns, and then from Cairns to KIX. It's also possible to find it on Ita matrix if you set a minimum layover (oddly enough, minconnect 150 was sufficient, even though the 6am combination JQ952 & JQ15 has a connection time of 3h 50m).

Questions I have:

Why was I unable to find this flight option? Do flight searches assume that an option that has a long layover is always inferior to one with a shorter but sufficient layover? Is Jetstar somehow reluctant to advertise alternative options for flying from Sydney to Osaka, either because it wants to flog 6am Sydney flights, or because it doesn't want to provide overnight accommodation for people in Cairns on a Saturday night?

What can I do to find this option, and other competing options using either Cairns or any other airport, without already knowing that it exists?

tl;dr: The nature of the way fares have been set up here happens to make it hard to search for JQ with an overnight stop in CNS, and some of these possibilities will be missed. Using the multicity search forces the pricing engine to consider going via CNS instead of other routes. Matrix finds it without a hint because it is better.

JetStar has fares filed on the Sydney–Osaka market, but none of them are valid for connecting itineraries. This complicates the search.

My speculation is that JQ has done themselves no favours in the structure of the fares they have published.

I took a look at the public fare tariff that JetStar (JQ) has published on the Sydney-Osaka market.

Each fare on this market that JQ has published contains the following restriction in the "Flight Applications" category.

FLIGHT APPLICATION 
 THE FARE COMPONENT MUST BE
 ON DIRECT FLIGHTS.

Just to be sure, the same restriction is repeated in the "Transfers" category.

TRANSFERS 
 TRANSFERS NOT PERMITTED.

This means that you cannot use any single JQ fare on SYD-OSA to build your desired itinerary. Instead we have to go down a more complicated route of using multiple fares.

Pricing itineraries with multiple legs using a single through-fare.

Usually when a flight search engine begins searching, it will start by looking at the fare tariffs that are published on the market the traveller desires. In this case, your market is SYDOSA, that is, Sydney (SYD) to Osaka (OSA).

Now it is computationally quite easy to sort these fares by price, and then, from lowest to highest fare, for each fare, try to find some set of flights between the origin and destination on which that fare is valid. Each flight set has some taxes and fees associated with it which must be added to the cost of the fare, and from there, the set is then be ranked by some suitability factors (for instance, total time of travel). Finally, some small subset of this enormous number of options is ready to present to the user.

Pricing an itinerary by combining multiple fares.

But that doesn't work for the JQ fares.

An alternative approach is needed. We split your itinerary in two halves. We look first for valid fares between SYD and some intermediate connecting point, then we look for fares between the connecting point and OSA, and then we repeat the exercise given above for those two halves of the itinerary. Then we have to check whether the fares in question allow themselves to be combined together. Finally we need the actual connecting flights to be reasonable. Then we repeat this for all the candidate connecting cities. (Each pair has its own list of candidates, we won't be considering SYD-AMS-KIX, for example.)

We can also repeat the above, covering the itinerary with three or four fares, or more, usually at most sixteen.

This is hard work. You can't just pick up any two random fares and glue them together. Just to illustrate, the JQ fares on SYD-CNS have the following restrictions in relation to combinations.

COMBINATIONS 
 END-ON-END
 END-ON-END COMBINATIONS PERMITTED WITH DOMESTIC/
 INTERNATIONAL FARES. VALIDATE ALL FARE COMPONENTS.
 SIDE TRIPS PERMITTED WITH NO RESTRICTIONS. FARES
 MUST BE SHOWN SEPARATELY ON THE TICKET. TRAVEL MUST
 BE VIA THE POINT OF COMBINATION.
 PROVIDED -
 COMBINATIONS ARE FOR CARRIER 3K/4M/9W/AA/AC/AF
 OR FOR CARRIER AY/AZ/BA/BL/CX/CZ
 OR FOR CARRIER DL/EK/ET/EY/FJ/FM
 OR FOR CARRIER GK/JL/JQ/KL/HX/LO
 OR FOR CARRIER LA/LH/LP/LX/LY/MH
 OR FOR CARRIER MU/NF/PX/QR/QF/QV
 COMBINATIONS ARE FOR CARRIER RJ/SB/TN/TK/UA/UL
 OR FOR CARRIER VN/XL/AI/JJ/DE
 OR FOR CARRIER KA/LJ/MK.
 OPEN JAWS/ROUND TRIPS/CIRCLE TRIPS
 FARES MAY BE COMBINED ON A HALF ROUND TRIP BASIS
 -TO FORM SINGLE OR DOUBLE OPEN JAWS/ROUND TRIPS/
 CIRCLE TRIPS.
 PROVIDED -
 COMBINATIONS ARE WITH ANY FARE FOR CARRIER 3K/4M/
 9W/AA/AC/AF
 OR FOR CARRIER AY/AZ/BA/BL/CX/CZ
 OR FOR CARRIER DL/EK/ET/EY/FJ/FM
 OR FOR CARRIER GK/JL/JQ/KL/HX/LO
 OR FOR CARRIER LA/LH/LP/LX/LY/MH
 OR FOR CARRIER MU/NF/PX/QR/QF/QV
 COMBINATIONS ARE WITH ANY FARE FOR CARRIER RJ/SB/
 TN/TK/UA/UL
 OR FOR CARRIER VN/XL/AI/JJ/DE
 OR FOR CARRIER KA/LJ/MK IN ANY RULE AND TARIFF.

Every fare on the whole ticket needs to be happy with these combinations.

(This is why we have the rise of "hacker fares", which is when we use several fares on several different tickets. When different tickets are involved, the combination restrictions don't apply.)

Why can't typical flight searches find this, even when you are specific?

Usually the result set is calculated in advance, and then the filters on the web page simply exclude certain results. If the engine did not discover what you wanted in the first pass, changing the filters does not fix that.

Why does the ITA Matrix have no difficulty with this?

Simply put, ITA Software is far and away the best at solving flight pricing problems. However, even Matrix struggles at times and there is still much value in understanding what is going on.

Why does the multicity search find it?

Using a multicity search does two things.

First, it forces the engine to consider the city you stop at. That dramatically changes the shape of the search. Itineraries on SYD-KUL-KIX cannot be considered anymore, and no time will be spent on them. That time is now dedicated to SYD-CNS-KIX.

Second, and perhaps more importantly here, some flight engines will consider the stopping city almost as a "hint" as to where a fare break point should be. The fare break point is the point between one fare and the next, so for a SYDCNS fare end-on-end with a CNSOSA fare, the break point is at CNS, whether or not you actually take a stopover there.

Now technically, there is no reason why a fare break need coincide with an actual stopover, because you can have a through-fare that permit stopovers midway through the fare. Nonetheless, I have found the multicity search is an invaluable way to communicate to the engine the fare break points it should investigate.

 On your specific questions.

Do flight searches assume that an option that has a long layover is always inferior to one with a shorter but sufficient layover?

Generally, yes, at fixed price; unless you specify otherwise.

Is Jetstar somehow reluctant to advertise alternative options for flying from Sydney to Osaka, either because it wants to flog 6am Sydney flights, or because it doesn't want to provide overnight accommodation for people in Cairns on a Saturday night?

If JQ wanted to discourage selling this route, they have a myriad of ways available to them to increase the price, and that would affect all sales channels (or whichever specific sales channels they wished). JQ could also totally disallow the combination that Matrix and multicity search finds by stipulating as much in the fare rules.

What can I do to find this option, and other competing options using either Cairns or any other airport, without already knowing that it exists?

Keep playing, keep learning. Air fare pricing is complex and full of nuances, idiosyncrasies and subtleties.

Look at each of the connecting cities specifically. Find out who flies what routes and on what schedules. Then you can focus on what you want more narrowly and give the pricing engine more of a chance to find what you want. Learn to read fare rules and ideally obtain access to the fare tariffs through a tool like ExpertFlyer or KVS.