As mobile networking continues to experience increasing popularity, the need to connect large numbers of wireless devices will become more prevalent. Many recent proposals for ad hoc routing have certain characteristics that may limit their scalability to large networks. This paper examines five different combinations of modifications that may be incorporated into virtually any on-demand protocol in order to improve its scalability. The scalability of current on-demand routing protocols is evaluated through the selection of a representative from this class of protocols. The performance of the un-modified on-demand protocol is compared against that of it combined with each of the scalability modifications. Each scheme's behavior is analyzed in networks as large as 10,000 nodes through detailed simulation. Based on the observations, conclusions are drawn as to the expected scalability improvement that can be achieved by each modification.