They don't have to store it. The network will forget about your 0-confirmation transactions after a few days if you don't rebroadcast them.