I really wouldn't worry about taxes. You'll pay several hundred dollars surcharge to leave the UK in a premium cabin (anything but economy). But otherwise taxes from other ports in Europe will be in the region of a hundred or so dollars. Not worth losing a seat over. (No additional taxes flying in to the UK, only out).
Booking at short notice all depends on the route. You can often find seats with creative routes (for example MEL/SYD to Bali on Qantas followed by Emirates out of Bali to anywhere in Europe). Or you can look at second tier carriers (Air India for star alliance for example). And single seats always easier than two or more. Using the multi city tool can find departures AU-Asia followed by connections from Asia to Europe, these connections may not show up on a single point-to-point search.
Failing all of those, and any last-minute release of seats (like Cathay or Lufthansa, or even emirates), you either change dates or buy a ticket.
I think your return dates may also run into school holidays making availability harder?
(Appreciate this is an SQ thread, but I think the OP mentioned availability of points on other programs and carriers)
oh yeah sorry, I got my lingo wrong, I just lump taxes and surcharges into the same categeory, to me whether I pay surhcarges or taxes doesnt matter, its all about the final dollar value