The protection of critical maritime infrastructures (CMIs) is of paramount importance for the efficient functioning of global trade, the secure exchange of data, and the maintenance of international security. A significant number of CMIs are situated in remote locations, with an increasing reliance on uncrewed vehicles (UxVs) for surveillance and protection. For the effective coordination of their missions and the efficient exchange of data, UxVs require the capacity for self-organization through spontaneous Mobile Ad-Hoc networks (MANETs). This paper presents an extension of a reactive Ad-Hoc routing protocol, designed to optimize communication in Multi-Domain environments involving uncrewed underwater (UUVs), surface (USVs) and aerial vehicles (UAVs). The protocol introduces message types to identify gateways that act as intermediaries between underwater and above-water communication, minimizing latency and routing complexity. The proposed approach was validated through the utilization of Matlab-based simulations and practical experiments, employing Raspberry Pis and acoustic modems. The findings highlight measurable improvements in communication efficiency, enabling seamless data exchange between UxVs, which enhances the resilience and protection of CMIs in complex maritime environments.