Unmanned Aeronautical Ad-hoc Networks (UAANETs) are infrastructure-less and self-organizing networks that are formed by small and medium sized Unmanned Aerial Vehicles (UAVs) that are deployed for a wide range of civilian and military applications. Having a reliable routing protocol for communication between the UAVs is critical. Our goal in this research is twofold. First, we enhance one of the existing routing protocols, the Reactive-Greedy-Reactive (RGR) protocol. In doing so, we propose the Optimized-RGR. Secondly, we propose the Enhanced Gauss-Markov (EGM) mobility model for UAANET simulations to replace the widely used, but unrealistic, Random Waypoint (RWP) mobility model. Simulations performed using the OPNET simulator show that Optimized-RGR outperforms RGR. There is a 5.3% increase in Packet Delivery Ratio at a negligible cost in latency. Furthermore, realistic mobility models, including EGM, show a lot of network partitioning. Therefore, this should be taken very seriously when developing a routing protocol for UAANETs.