China could of (some say did) establish trading posts in Australia. In fact I think it should have LESS provinces, I would prefer an balkan or spanish province to a 500 miles of useless sand or jungle. However the thought of colanization should be raised... who knows? What if magellian or some French/Spanish/portugese sailor found newzealand?, it would be like the philopines or a mass genocide like cuba/haiti. The position would be quite stratigical, a good solid base in the pacific. (actually i've seen a french newzealand in my game =)).
Been a loose crusader kings player I would've liked if the powers could, while having national stratergies have a sort of randomization and luck in finding their powers... columbus's voyage could have easily failed, the portugese could have abandoned their adventurizm and economic decline of europe would have continued... although I like to see a big green Brazil and not a mixture of venician/dutch/English colonies, I think taking austrias blobatization AI would fit well