Search plays an important role in ubiquitous computing. In this paper, we investigate the expected cost and latency of three unstructured search schemes: broadcast, TTL-based, and random-walk-based search schemes. We build a unified analytical model for unstructured search schemes. We demonstrate, through simulation, that the different search schemes exhibit very different cost and latency tradeoffs, leaving large gaps in the performance landscape. We propose randomized mixing schemes to bridge such performance gaps and bring out new Pareto frontier that offers more diverse performance choice for applications.