In real life, Labor tried to make the election about trust/integrity of government, due to the children overboard inquiry, the GST (despite the fact that Howard took it to the electorate), and Rudd's unsubstantiated claims about the government's involvement in the AWB scandal.
The Coalition turned that around, with Howard asking during the "election announcment" press conference, words to the effect of "the question the Australian people need to ask is 'who do they trust to manage Australia's economy and keep interest rates low?'"
I read an article after the election that post-election focus group polling showed that Labor's advertising of "vote for Howard, get Costello" had somewhat backfired, not because people didn't believe it, but because they credited Costello with the economy, and the Coalition was strongly supported in issues polling as the party to better protect the economy. I think this is an important point to note when considering this scenario.
I think that in this scenario, the Coalition would still try to make the economy the main issue, because it was such a strong positive for the government. They wouldn't be able to run the "L-Plate Latham" ads, but instead would probably remind people that Beazley had been Finance Minister back in 1991. The ads that actually ran, one of them showed interest rates under various Labor Prime Ministers, and one showed how much interest repayments would go up if the interest rate rose by a certain percentage - finishing with "and if they rose to the average level when Labor was last in office" - I think with Beazley as leader, you'd find a "and if they rose to the level when Kim Beazley was Finance Minister" interest rate comparison in there.
Labor, on the other hand, would try to make it about IR, given Costello's involvement in the Dollar Sweets case.
Here are some of the actual Coalition ads that ran during the 2004 election campaign. Some of these would not take much adaptation to make them a Costello vs Beazley election campaign ad.
Mark Latham and Interest RatesWish Me LuckInterest Rates and LaborMark Latham and the Liverpool CouncilMark Latham and Council feesEconomic JourneyAs you note, without a Senate majority, there would be no Workchoices legislation. By 2007, with the US economy becoming increasingly wobbly,
here's an article where he warns of an upcoming "economic tsunami" in the lead up to to the 2007 election, thus I think you'd find economic stability being the theme in 2007 as well. Of course, the world economy continues to decline after then. Assuming that the Australian economy gets by recession-free, as it did IRL (predominantly due to the mining boom, fuelled by Chinese economic growth), the 2010 ads (and indeed, the press conference when the economic statistics are release) would probably have Costello reminding people that when Labor was last in office, we had the "recession we had to have" but that under the Costello Government, Australia withstood the largest economic crisis since the great depression, without slipping into recession.