You can store the state in FLASH indeed, and have a rotating scheme to reduce wear. However, in practice it should also go fine if you store the information outside your system.
Suppose you have a phone that remotely SETs the relay. Now the relay gets powered off and on through some fluke. The next time it is powered on and its state is the same as that on the phone, because that device is oblivious to this entire sequence of events.
Next time the phone remotely does a RESET and the relay will toggle as expected.
If (1) someone else does change the state of the relay and (2) the chip is recycled, then you will be out of sync with the actual state for one cycle. After sending a SET or RESET it is synchronized again.