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.
Then what's the point of broadcasting a 'subscription' transaction with an nLockTime days or months into the future, if the transaction is just going to get dropped long before the time it is 'due'? Or am I misunderstanding the suggestion that was given for using nLockTime transactions for subscriptions?
Of course, I could still keep miner's disks pretty full if I broadcast say 1000 nLockTime transactions an hour. Basically if i want to force miners to waste 100 MB of disk space, I just have to transmit 100 MB of nLockTime transactions per day; each day when miners eliminate old cruft, they just get more from me. I get some 'friends' to do the same and now miners are wasting lots of disk space and burning lots of network bandwidth accepting these transactions.