I had a similar problem finding availability on this route. I'm pretty sure that BA release 2F and at least 2J award seats on every flight but, as they're extremely popular, you need to book 11 months ahead. You can improve your chances by searching for flights with a stopover in SIN or BKK - I found that even a < 24 hour stopover improves your chances by looking for other flight combinations (e.g. using the BA17 MEL flight as far as SIN and then transferring to BA15 for SYD). I also discovered that if you phone the exec club they can see availability that you can't yet see online (e.g. at the moment, you can't yet search for availability next June but if you phone up, they will be able to see this). Obviously, this would incur the £15 per person off-line fee but it's probably worth paying that to be sure of getting the seats.

For my own booking to SYD next year (2 seats in F) I had to use the BA17 / BA15 / switch in SIN trick and made a phone booking to get the return flights I wanted before they could even be seen online.