South Australia 2010 and 2014
For two elections running, the South Australian Labour party has trailed the LNP in the TPP vote, but still have remained in government. The Liberals keep running up their margins in the base, but cannot quite grab the all important marginals.
Queensland under Joh Bjelke Petersen was also amusingly gerrymandered to the benefit of rurals, so the ALP often won the popular vote but was kept out of office.
That was once the case in South Australia too (the "Playmander"). Indeed it seems to have been something the Australian Right were rather keen on.
Nothing to do with the Australian Right. In Queensland, Bjelke-Petersen merely extended what had been initially instituted by the Labor Party, who allowed regional cities such as Rockhampton, Mackay, Cairns, Townsville, etc, to be under-represented (incidentally, Labor polled very well in the regional cities at that time). Bjelke-Petersen extended it to include rural areas as well as regional cities (and rural areas to be over-represented even more than the regional cities were), but it was still Labor that had introduced this malapportionment.