What it goes back to is that stations test their music, and they don't play songs if they're not hits, or near hits, to the target demo. What you're describing isn't rare at all. "Under The Bridge" by RHCP is popular with the heavily male audience of KZEP as well as the heavily female audience of KSMG.
As for your question as to whether anyone is requesting the song, the benefit of requests has been debatable for a long time. Only a small fraction of the audience will ever call the request line. Besides, a station playlist consists of usually around 500 songs, and you won't get 500 requests. So what if nobody's buying the CD anymore? Maybe they already have the CD. Or maybe, like everyone else, they hear a song they like but don't bother buying the CD for whatever reason. I'm sure you like plenty of songs you don't own!
Finally, that the song aired on two stations at roughly the same time isn't particularly rare either. While a classic rock and a hot AC may not have the same categories of music, the rotations will be similar. No, classic rock stations won't have powers that rotate every 4 hours like a hot AC will, but the more popular songs will still be played more often. There really aren't as many possible variations of clock structures as you might think. I used to joke that, when programming an oldies station, you really only needed one category: "Powergold." However, you wouldn't want "Stop in the Name of Love" or "Pretty Woman" to have the same probability of appearing as Bobby Goldsboro's "Honey!" So, you structure your clock to make sure that can't happen.
