One of the key components affecting the overall performance of hybrid ad hoc networks is the algorithm used to discover and select Internet gateways. We have analytically modeled existing proposals (i.e. proactive, reactive and hybrid gateway discovery) showing that each of them is most suited only for a limited range of network parameters. We propose a new adaptive gateway discovery algorihtm called "maximal benefit coverage" based on the dynamic adjustment of the scope of the gateway advertisement packets. We show through simulation that ability of our proposed scheme to adapt to the changes on the network conditions allow it to outperform existing mechanisms alternatives over a variety of scenarios and mobility rates.