Adaptive message caches are disclosed for packet replay and/or flood protection in mesh network devices. The adaptive message cache includes a replay protection area (RPA) and a flood protection area (FPA). For each received packet, a packet security processor compares packet metadata to metadata entries stored for prior packets within the RPA to provide a replay protection check. If a replay protection check is not passed, the packet is dropped. If passed, the packet security processor compares the packet metadata to metadata entries stored for prior packets within the FPA to provide a flood protection check. If the flood protection check is not passed, the packet is dropped. If passed, the received packet is authenticated for the mesh network. Entries within the RPA/FPA are then updated using the packet metadata. Further, the sizes of the RPA and FPA can be adaptively adjusted based upon the packet metadata.