Hi MisterAviator,

I do not have any HA miles but assuming HA miles award availability on VS is the same as for Virgin miles, some hints;

(1) Upper Class LAS-LGW ( Gatwick not Heathrow) availability is very tight ( lots of demand and only 14 upper class seats per aircraft). Availability form LAX & SFO to LHR is generally a lot better ( but I would book well in advance). South African routes are also popular but given the current climate, more seats may be available.
Not sure on Premium Economy but I think there is better availability ( but it is a very long flight via London to South Africa)

Good luck in finding something.

Regards

TBS