"My band plays a lot of one night dates in a variety of circumstances. We usually have time for a pretty thorough sound check, but often find that things still go wrong when we first start playing. At the very least what sounded good in the check no longer sounds good."

This is common. As rooms fill with people the acoustics can dramatically change. If you're in a room with hard (brick) surfaces and use an RTA to tune your PA, you will be pulling out lots of upper midrange frequencies because they are being reflected off of the hard surfaces. Once you replace those surfaces with the bodies of humans those frequencies begin to be absorbed and your room EQ is now all wrong. You either need to adapt to this on the fly, or if you already know how the room sounds when full of people, set your PA accordingly.

I sometimes see people agonizing over the wrong things in sound check. I've seen bands spend an hour getting the most crushing kick drum sound you've ever heard, only to rush though other phases and realize when it's too late that the guitar amp is pointed directly at the floor tom mic (which is really interesting when you use noise gates on the toms). Unless you just have hours and hours to check every detail, it's best to focus on the big picture as much as possible. Of course, you should make sure all the lines are working and have a good, clean signal, but once you have the basic tones together it's best to do most of the rest of the work with the whole band playing. That's where you'll really uncover a lot of the problems. Then it's just a matter of systematically attacking things one by one. You may need to stop the band for a few minutes to address specific things, but in general you should try to keep the momentum going so the players don't get bored and distracted. A jam session breaking out is not going to help the sound man as much as the band playing the actual songs that will be played. Finally, make the last song of sound check the first song that will be performed in your set. This helps get a lot of the little things in order so the sound man can concentrate on making the broad changes that invariably must be made during the first few numbers of the night.