It could be possible that the availability is only for QF or BA, but I highly doubt that somehow. If QF can see something that BA also sees, it is likely fair game across the entire alliance (except for CX, perhaps). I could believe if QF only could see it...
Only thing that springs to mind is that are you searching as LHR-MEL/LHR-SYD or each leg separately? The availability can vary depending on how you search for the marketed sector(s). It is quite possible that you can get F on LHR-MEL (which goes via DXB), but if you were to search LHR-DXB and DXB-MEL, you wouldn't necessarily get F seats on both. Makes sense? Not really, but that's the way it is.
When you feed these flights to the agent, you may need to tell them to try and get the entire sector and flight you have found, i.e. "<date> Qantas Airways Flight QF 10, London Heathrow to Melbourne, Australia"; viz. don't mention DXB (they may bring up that it is a 1-stop flight, which is fine). Don't try and feed them the individual segments, or it may 'fail' as you've found out. This also works the other way, i.e. if you find F seats on the individual sectors but not on the marketed single long one.
Now if that doesn't work then I have no idea.