- Send a message to someone whose phone is off

- turn off your phone

- get that person to turn their phone on

- they receive the message.

Where was it stored, if not in WhatsApps servers?

Whatsapp backs up unencrypted messages to Google cloud on Android and whatever it's called for Apple.

The government can just ask them to turn over those. (note that this is legally very different from forcing someone to unlock a device)