Techniques for stateful connection optimization over stretched networks are disclosed. In one embodiment, hypervisor filtering modules in a cloud computing system are configured to modify packets sent by virtual computing instances (e.g., virtual machines (VMs)) in the cloud to local destinations in the cloud such that those packets have the destination Media Access Control (MAC) address of a local router that is also in the cloud. Doing so prevents tromboning traffic flows in which packets sent by virtual computing instances in the cloud to location destinations are routed to a stretched network's default gateway that is not in the cloud.