The proximity service using Bluetooth and/or P2P WIFI enabled mobile devices for people's social interactions with other users who come into their close proximity is becoming an important means for people to conveniently and efficiently expand their social networks. Proximity mobile social networks (PMSNs) are usually built in ad hoc mode to allow information sharing and interaction among users in proximity-based communities through cooperative services. Reliable message propagation serves as a fundamental component for various applications of PMSN (e.g. propagating advertisement, probing nearby friends, etc.). We propose an architecture for message propagation in PMSN applications in highly dynamic and user-dense environments, such as in student dormitories, crowded sports, and shopping centers. The proposed message propagation relies on node mobility and periodic retransmission of a message. We conduct elaborate simulations under different mobility models, and show that the proposed reliable message propagation demonstrates excellent reliability, efficiency, and robustness.