The problem of searching for mobile users in cellular networks is addressed in this study. Previous studies addressing this issue have focused on the problem of searching for a single user. The underlying assumption for this approach is that some straightforward strategy of searching for multiple users can be easily derived from a single user search strategy. Unfortunately, this assumption is violated very often in practice. As it is shown in this study, the problem of maximizing the expected rate of successful searches under delay and bandwidth constraints is NP-hard. Given the conditions that each search for a single user must be over during a pre-defined time period, and that the bandwidth available for search operations is bounded from above by a pre-defined constant, when the potential locations of different users overlap, the derivation of an optimal concurrent search for many independent users from a set of optimal single user searches is NP-hard. Unfortunately, very often the potential locations of different users overlap. In reality, a cellular network has to serve many competing search requests sharing a limited bandwidth. Since the problem of maximizing the expected rate of successful searches under delay and bandwidth constraints is NP-hard, this study proposes an approximation algorithm, that is optimal for most probable cases, and nearly optimal for the worst case condition. Even under the worst case condition, the proposed method can potentially increase the expected rate of successful searches by 100%. Moreover, the proposed search strategy outperforms a greedy search strategy, that considers only the users' location probabilities and ignores their deadline constraints. Under certain conditions, the expected rate of successful searches generated by the proposed method is twice the equivalent rate generated by the greedy search strategy. In addition, the proposed search strategy outperforms a heuristic algorithm that searches around the user last known location.