Flies
They were the worst (though pretty only) evil on the journey and accompanied us especially on the first part from the Kakadu NP up to Broome. People told us that the plague of flies havn't been that bad since years. Down the western coast and in the south of Australia too, there were still some regions where the beasts became annoying to us. Only in the east they let us alone (except the VisitorCentre in Townsville).
Only in mentally preparation for the journey: all the dots on this picture are flies - despite constantly shooing them away
Unfortunately there is not much you can do to protect yourself against the nice fellows. We had a mosquito net for the head and when it was to awful (there are really various bad kinds of flies - as cyclist you unintentionally become a fly expert), we did not make a rest, because the airstream helped a lot (It's sort of weird, but sometimes we were really happy about headwind). Long clothing helps too. Its better to sweat than to endure the permanent tickling of them crawling around on the skin.
Tip: Do not unwrap albuminous food! Flies go beserk if they smell for example eggs or fish. That is because they need a lot of proteins for their egg deposition. Therefore they also favour eyes, mouth, nose and ears to crawl inside, because there they get, what they search for.
Just a tip: Don't try to eat your meal hiding behind a mosquito net. It's better to eat while riding the bike!
By the way the Australian fly plague became so extreme due to the sheep and cattle imports during the colonisation times, because flies use the dung of these animals as hotbeds. Hence the Australians search for a beetle or something similar, who feeds on this "imported" dung. Thus the flies would not have so much possibilities to increase any longer.