Oblivious message retrieval (OMR) allows resource-limited recipients to outsource the message retrieval process without revealing which messages are pertinent to which recipient. Its realizations in recent works leave an open problem: can an OMR scheme be both practical and provably secure against spamming attacks by malicious senders (i.e., DoS-resistant) under standard assumptions? In this paper, we present \(\mathsf {DoS\text {-}PerfOMR}\) : a provably DoS-resistant OMR construction that is 12x faster than \(\textsf{OMRp2}\) (a conjectured DoS-resistant OMR construction in prior works), and (almost) matches the performance of the state-of-the-art OMR scheme that is not DoS-resistant (proven by the attacks we show). To achieve this, we analyze the snake-eye resistance property for general PKE schemes, i.e., whether it is hard to encrypt an identical message under two public keys. We construct a new lattice-based PKE scheme: \(\textsf{LWEmongrass}\) , that is provably snake-eye resistant and has better efficiency than the PVW scheme underlying \(\textsf{OMRp2}\) . We also show that natural candidates (e.g., RingLWE PKE) are not snake-eye resistant. Furthermore, we show that a snake-eye resistant PKE scheme implies a robust PKE scheme, thus introducing the first robust lattice-based PKE scheme without relying on the KEM-DEM paradigm, avoiding its inherent inefficiencies. Of independent interest, we introduce two variants of LWE with side information, as components towards proving the properties of \(\textsf{LWEmongrass}\) , and reduce standard LWE to them for the parameters of interest.