Because I lost my iPhone 3GS headphones (those with microphone and remote control), I now tried to use the latest ones (from iPhone 4S). The microphone is working, but somehow the iPhone doesn't react of the remote control (Accepting calls, stopping the music, or changing the volume doesn't work at all). Are the new headphones generally incompatible with the iPhone 3GS, or is it a different problem?
I had this issue with my iPhone 4. Turns out some debris got in the headphone jack. As the 3GS is an older device, the contacts may be dirty.
Try taking a cotton swab with most of the cotton removed and dipping it in rubbing alcohol. While it's off, clean the sides of the headphone port on the 3GS.
Let it sit for five minutes and turn it on. See if that helps.
Another thing you can do is quickly and forcefully insert and remove the headphones in question to (hopefully) clear anything blocking the contacts.
Personally, I'd try the first option first.