Location cloaking has been shown to be cost-effective in mitigating location privacy and safety risks. This strategy, however, has significant impact on the applications that rely on location information. They may suffer efficiency loss; some may not even work with reduced location resolution. This research investigates two problems. 1) How to process location-cloaked queries. Processing such queries incurs significant more workload for both server and client. While the server needs to retrieve more query results and transmit them to the client, the client downloading these results wastes its battery power because most of them are useless. To address these problems, we propose a suite of novel techniques including query decomposition, scheduling, and personalized air indexing. These techniques are integrated into a single unified platform that is capable of handling various types of queries. 2) How a node V can verify whether or not another node P indeed locates in a cloaking region it claims. This problem is challenging due to the fact that the process of location verification may allow V to refine P's location within the region. We identify two types of attacks, transmission coverage attack and distance bounding attack. In the former, V refines a cloaking region by adjusting its transmission range to partially overlap with the region, whereas in the latter, by measuring the round trip time of its communication with P. We present two corresponding counter strategies, and built on top of them, propose a novel technique that allows P to participate in location verification while providing a certain level of guarantee that its cloaking region will not be refined during the process.