Worth Reading: VXLAN Drops Large Packets
Ian Nightingale published an interesting story of connectivity problems he had in a VXLAN-based campus network. TL&DR: it’s always the MTU (unless it’s DNS or BGP).
The really fun part: even though large L2 segments might have magical properties (according to vendor fluff), there’s no host-to-network communication in transparent bridging, so there’s absolutely no way that the ingress VTEP could tell the host that the packet is too big. In a layer-3 network you have at least a fighting chance…
For more details, watch the Switching, Routing and Bridging part of How Networks Really Work webinar (most of it available with Free Subscription).
I had a heuristic when troubleshooting that "if the problem was non-deterministic (or close to it), look at layer 2 first". Duplicate MACs, MTU, flapping spanning tree: generally something of that ilk.
DHCP has the Interface MTU Option but I doubt all clients honor it. And that wouldn't have helped in this case anyway.