I can certainly understand your issues in regards to timing. Even with the big show I do, I have manual access to all scenes just in case I should have to bump something along.
Using my idea of a heavily stepped scene for a song, unless you know what step you're on, forget it!! Once you're screwed, you're screwed until you go into the next song.
Another option you could explore depends on what you're doing. Are there any pre-recorded tracks? If so, you can transition those from a CD, DAT, MD(minidisc) or other playback device and into some low to midrange DAW, say Sonar Home Studio.
You can then sequence on a per channel basis using CC controllers assigned to channels in MyDMX.
This also requires 2 computers: 1 for sequencing, 1 for MyDMX. It also requires 2 MIDI interfaces, 1/machine. It also requires that you spend a LOT of time programming your controllers and DOCUMENT them(in case it loses them).
I just don't see how you can be in a win-win situation. You're at the mercy of the band. IF they throw a big change on the fly at you, thre's not much you can do, at least like IMMEDIATELY, everything takes a little bit of time. Of course, this is why good communication between the tech crew and the stage talent is so important.
You're obviously aware that MyDMX has a limitation in the number of scenes you can use per show file. Of course, I know you're not using that many scenes per song, and I'll bet your re-usable scenes are minimized due to the nature of the music. I certainly understand how that can work.
Somehow, I get the feeling that you're not working with sequenced tracks since the band seems to do the typical live "speed it up a hair" thing.
I think you're right. A DMX controller, along with MyDMX, a DMX combiner(so you can keep both live at the samt time and a OptiBranch/4(may not be needed after the combiner, but good to have anyways) might be some options to look at to allow you to get through transitions.
I'd also see what Jingles has to say about Compu. It may be you're just beyond what MyDMX can offer for your situation.