We had 'God Save The Queen' up until the 70s or 80s. The they changed it to 'Advance Austrlia Fair', which is equally as bad. But of course an anthem isn't meant to be a popular song, such as Waltzing Matilda (people still sing the wrong tune, believe it or not) which explains why it didn't get voted in.
It could have been worse, we all could have been singing
Deutschland Deutschland
Uber alles.