First, just to be picky, "in lava" and "in a burning building" are vastly different in ways that make them quite difficult to compare.
But beyond that, I disagree that you have nowhere to go from "if you fall into lava, you die." D&D is all about the exceptions.
If you get a magic charm that makes you immune to petrification, well then NOW you can go see how long it takes for Medusa to blink.
Situations can certainly arise for all kinds of survival in circumstances that are instantly deadly by default.
Someone earlier responded to "What happens to a hero in a burning building?" with "The same thing that happens to everyone else," paraphrasing of course. If the answer to both burning buildings and lava is "you die," there's not much granularity there. Either you die, or you're immune, with no middle ground.
If you try to introduce a middle ground with some magic charm that lets you make a Fort save to avoid petrification, well, why don't you just make that the default again? Getting into a staring contest with a medusa is
stupid and unnecessarily risky, but it could easily be something that a hero could choose to do at a certain point.
And, again, I would point out the whole "Perseus was a low-level hero" thing. A 3e medusa has a DC 15 gaze attack; if we're feeling charitable for Perseus, we could stat him as a 5th-level rogue with 14 Con, giving him a +4 Fort. That's a 50/50 shot to save, and with the medusa getting both the passive gaze when he looks at her and an active gaze on her turn, that means that if Perseus looks directly at her he's statistically going to lose that contest in one round. So as far as Perseus and other low-level heroes are concerned, you
can't get into a staring contest with Medusa. That shouldn't prevent the Hulk from staring at her nonchalantly and making catcalls because he's just that tough, because the assumptions for realistic vs. superhuman heroes are different.
I talked to the DM later and he was trying to set it up so we would start questioning what we had been told by Mr Bad. He never thought since we were a good party that we would kill the guards this way. He also thought we would have surrendered or left because of the archers.
This. This right here. The problem here isn't that high-level characters are nigh unto gods (which they are) or that bunches of mooks aren't a threat (which they aren't) but that (A) you were metagaming "Oh, the DM wouldn't send a non-level-appropriate encounter against us" and (B)
you decided to slaughter the guards despite being a theoretically good party.
Regarding CR, I quite often throw encounters against my parties that are CR +8 or higher by the rules at my party when faced head-on but easier if you take them on intelligently--like the medusa example above, it's
possible to take on 1000 archers yourself as a 15th level character, but you'd have to be a moron or suicidal to chance it when there are much better solutions and if you don't just charge in mindlessly it works out to more like a CR +1 challenge. So you were right to note that they were known for their archers and think that perhaps, just perhaps, they might have something that might make them actually a threat; CR is a terrible guideline, and DMs can throw ranges of encounters at you in any case, so it's
possible that they could have threatened you.
It's one thing to say "Gee, we've fought archers before, these guys don't have anything indicating that they're exceptional, I doubt they're a threat--kill them!" but entirely another to say "Gee, these guys are known for their excellent archers, and we don't have much experience against massed archers, but the DM wouldn't throw an encounter of too high CR against us! Charge!"
Regarding alignment, what in Baator was your party thinking? Why would your theoretically-good party, when faced with a misunderstanding and offered a chance to just talk to someone or leave, decide on the route of violence? Hell, I'm currently playing in a high-power game as a 10th level "monk" (i.e. a mostly-noncasting multiclassed monstrosity that fights unarmed and unarmored) who is a psychopathic chaotic evil missionary for a chaotic evil religion and who can slaughter pretty much anything with fewer than 7 HD that ends its turn within 100 feet of him, and even
he doesn't go crazy and slaughter everything in sight until he knows that they're actually
enemies.
The two problems with that scenario are really that your DM was expecting your party to act a lot differently than you did, and that the rogue went off and provoked them without party consensus. If I were the DM in that situation--well, first of all, there is no one in my group with better rules knowledge, so no one would pull the "By the CR guidelines..." stuff with me, but that aside, if I were the DM in that situation, I'd be surprised with a good party suddenly changing their tune as well. I'd say a chat with your group and DM about good vs. bad metagaming and playstyle expectations would be a lot more useful in your case than making houserules to fix what ain't broke.