May is in peak tourist season for the UK, so seats would be pretty scarce.
There is some availability in June (at least June 5), but doubt if that helps too much.
Qantas releases a small number of seats in each class on flights. How many they release (and if/when they release more) is not really known.
Qantas FF's can access the seats 353 days in advance, which means that people have already grabbed the available seats anything up to ~280 days ago (May/June last year).
There are chances that more seats will become available leading up to May, but I don't know the likelyhood of this happening.
Frequent Flyer Friend (
http://www.frequentflyerfriend.com) is one way you can try and keep track of newly released seats.
Alternatively, what you might want to try is some alternative routings using a Partner award. Eg. MEL-HKG (Qantas)/ HKG-LHR (Cathay) or something similar. You would need to call up Qantas and ask them to do some searches for you to try this. You also pay an assisted booking fee of 2500 points per passenger if you book this way.
You could also try and get flights to London from Brisbane or Sydney, then get a domestic award (or paid ticket) and then connect to it.
As for your upgrade chances, a lot of that depends on your status with Qantas. Are you Platinum or Gold? If not, I think your chances are very low. Others may be able to give a better idea of the kind of load on flights to LHR in May.
Linear Mode
