Norfolk Island, a self-governing Australian territory between Australia and New Zealand, was uninhabited when Captain James Cook stumbled upon it in the late 18th Century. This was several decades after the publication of Gulliver's Travels. The island holds a population of over two thousand people today.
Norfolk did apparently host a Polynesian settlement several centuries before its rediscovery, but their society vanished long before its first European visitors. They did leave behind some imported remnants of their colonization, including banana trees, New Zealand flax plants, and Polynesian rats.
If you're looking for something completely virgin, there's nearby Lord Howe Island, which today has a population of several hundred and doesn't seem to have ever been discovered by anyone before the late 18th Century (its discoverers were, in fact, on the way to found a penal colony on Norfolk).