I'm also iffy about rotating setlists. I think that Portnoy's influence helped keep the band more spontaneous, especially with the jamming they used to do at gigs, but as a fan I like to know what I'm getting into.
I was discussing this recently in another thread, but Clutch changes their setlist around every night. Each member takes turns picking the setlist, sometimes taking the city into account, sometimes just playing whatever they feel like. I know that I've personally gone to two or three Clutch shows after looking at their most recent setlists and thought, "Oh man, they're playing some of their new, super melodic bluesy stuff!" then shown up to a gig and been treated to the bassist's choice of 90% early hardcore Clutch songs yelling like cavemen.
From the musician's standpoint, I think Dream Theater is at a point in their career where they are becoming/have become a package band, same with Maiden. They put together a package and really drill it while touring the same set every night and I think that works to their advantage. This is definitely true of LaBrie, who is able to train his voice to a specific set of songs instead of being thrown for a loop when Mike Portnoy whimsically decides he wants to put The Killing Hand on the setlist.