Wow, that progression is all over the place.
A knowledge of the fretboard helps above anything else (i.e., learning every note everywhere, and being able to think of scales all over, rather than in "patterns" ). In addition, you could stick by those modes and figure out good ways to transition smoothly from each to each. (For example, you shouldn't jump more than a few steps to the next note on a chord change).
You don't have to stay diatonic to each chord (that's what jazz is all about, right?
) by any means. Although what I'm about to suggest here won't make it any easier than it is, regardless, I would recommend also studying each chord so you can add tensions (altered tones, as you mentioned above) to make the harmony more interesting. I.E., playing Bb over that A7 would imply, for as long as you play the Bb, an A7b9; B7 + G# = B13, etc.
But the most important thing is the melody. If your solo just sounds like a bunch of notes strung together (whether it follows the harmony or not), it of course has to sound good.
...and solo through the correct modes.
Remember, a wrong note is never a wrong note if played with conviction.