Is it possible that a store with memory_order_relaxed never reaches other threads?

This is all the standard has to say on the matter, I believe:

[intro.multithread]/25 An implementation should ensure that the last value (in modification order) assigned by an atomic or synchronization operation will become visible to all other threads in a finite period of time.