Okay, but the relay isn't required to store my message and they can delete my message whenever they want. The only way I can guarantee my message is stored for as long as I want it to be is for it to be stored on my local device or my own relay?

That's right It's also worth highlighting the fact that whilst notes MAY be removed, they CANNOT be modified (else they wouldn't validate)