The research on P2P systems which support skewed key distributions has rapidly advanced in the recent years. Yet, the assumptions on the skews we are dealing with remained pretty simple: most of the existing literature assumes simple monotonous key distribution skews. However, this is not always the case. For example, Gnutella filename traces show that complex key-distributions rather than monotonous skews occur in practice. We show that one of the seminal P2P systems which support skewed keys - Mercury, performs poorly given such complex distributions generated from the trace of Gnutella filenames. We discuss the shortcomings of such state-of-the-art techniques. We present an overlay network Oscar, based on a novel overlay construction mechanism, which does not depend on the key-distribution complexity. We demonstrate through simulations that our technique performs well and significantly surpasses Mercury for such realistic workloads.