Systematic exploration of the observable parameter space, covered by large digital sky surveys spanning a range of wavelengths, will be one of the primary modes of research with a Virtual Observatory (VO). This will include searches for rare, unusual, or even previously unknown types of astronomical objects and phenomena, e.g. as outliers in some parameter space of measured properties, both in the catalog and image domains. Examples from current surveys include high-redshift quasars, type-2 quasars, brown dwarfs, and a small number of objects with puzzling spectra. Opening of the time domain will be especially interesting in this regard. Data-mining tools such as unsupervised clustering techniques will be essential in this task, and should become an important part of the VO toolkit.