I’m not so familiar with the USA routes so I’ll leave that to someone else. I can give you a few pointers on the routes via Asia.
- I'm duty bound to say "Points plus Pay" is not an value-effective use of your hard earned Velocity points. Look to book outright points tickets.
- May is usually one of the cheaper months to fly so there should be availability.
- Velocity points means flying with Virgin, Etihad or Singapore
Looks like you have enough points for Aus to UK economy returns. If that's your preference then
- Start on the Virgin site for flights from Aus to UK. Build up your flight, i.e. start with Aus to Singapore or Abu Dhabi as they are the two main routes.
- Once (if) you find those first sectors then look for connecting flights. Remember that Singapore and Etihad fly to multiple cities in UK. Try them all. Once you have located availability, you can book. Outbound and return flights can be booked separately with no disadvantage.
If you want to do the Business class sector, the natural place to look would be Singapore. BUT Singapore to Europe in Business is 68,000 Krisflyer Miles (after online 15% discount). So you'd need ~270K for return which is more than you have. 266K Velocity could be transferred to ~ 197K Singapore Airlines KirsFlyer Miles. That might just be enough for Business one way and Econ back.
I’m afraid to say that even this isn’t great value as Aus to UK is only 72K KF. Perhaps you could go oneway paid economy and return Business. Though I’ve not priced up one way there are some options out there … Scoot to Athens if you’re feeling brave. That said I had a quick look at MEL-MAN/LHR around 15th May and couldn’t see any availability.
If you do want to explore the Singapore option, create yourself a free Krisflyer account and explore away. They will allow you to search without having any points in your account and they have more seats available for their own frequent flyers. If yo do find something it’s easy enough to transfer the points across.