The volume on my iPhone decreases randomly
With the more information supplied:


the volume issue occurs with and without headphones
the volume issue occurs with and without a case


The only conclusions I can come to are that the iPhone 4S is either faulty, or there is a software glitch causing the issue.

Addressing the second issue, Apple will recommend you perform a DFU restore to factory settings to rule out software.  If the issue persists, then in all likelihood there is a hardware issue present.

I did find this link to a discussion for other iPhone 4S users with the same/similar issue (or with the Volume Up), at least one of which was resolved by the Genius taking the iPhone apart to find a piece of material in the switch assembly causing the issue.