To meet the demands of 6G wireless systems operating in high-mobility scenarios, this paper presents a design of a random multiplexing (RM) communication system that is both storage-efficient and highly reliable. In principle, RM with cross-domain memory approximate message passing (CD-MAMP) can achieve replica maximum a posteriori (MAP)-optimal performance by constructing a fully dense equivalent channel matrix. However, its practical implementation is hindered by the large storage overhead of conventional interleavers and by performance degradation in severely ill-conditioned channels, which existing related work (focusing on interleaving and transform designs) fails to address simultaneously. To overcome these issues, we develop a storage-efficient and highly reliable system that integrates RM with CD-MAMP, referred to as RM-MAMP. Specifically, we propose a Logistic chaotic mapping interleaver with a quantitative parameter-selection criterion, and a dual-stage high-order permutation polynomial interleaver, both of which achieve nearly identical bit-error-rate (BER) as fully random interleavers while reducing the interleaver storage from O(N) to O(1) and significantly lowering interleaver signaling overhead. We further propose a highly reliable interleaved transform framework, comprising an interleaved phase perturbation transform and a multi-layer interleaved coupled transform, to enhance the incoherence and diversity of the equivalent channel matrix. Simulation results show that the proposed storage-efficient interleavers maintain BER performance comparable to fully random interleavers, while the highly reliable transforms provide over 4 dB gain in severely time-varying channels, confirming the dual benefits of reduced storage overhead and improved robustness for the enhanced RM-MAMP system.