Coles and 'Flybuys' are only linked to Velocity, not sole contracted, and many other businesses that had links to Ansett are still not contracted back into the loyalty program schemes. There's a big market of possibilities. Just depends what you have to trade to tap in.
PS most of the car rental, hotel chains and other travel extras tend to just affiliate now with airlines rather than sole contract. Rex just has to prove they can provide X customers and they will make a discounted deal for their passengers.