The disclosed apparatus may include (1) at least one communication port that facilitates communication between a source computing device and a destination computing device via a path within a network and (2) a processing unit communicatively coupled to the communication port, wherein the processing unit (A) monitors the network for any changes to the path that potentially affect a maximum transmission unit of the path, (B) detects, while monitoring the network, a change to at least one hop included in the path, and then in response to detecting the change to the hop, (C) identifies a packet size that corresponds to the maximum transmission unit of the path, and (D) tests the path for an increase in the maximum transmission unit by transmitting a packet whose size is larger than the packet size that corresponds to the maximum transmission unit. Various other apparatuses, systems, and methods are also disclosed.