First thing you need to do is get the manual for the amp and read the section on settings. I don't know why, but the actual useable range is very small on some of the controls, and they knew that.
On my MarkIII the bass is never over 1 with the shift pulled, and I don't run volume 1 over 7.5 or so, ever. Same with the lead. You might get it to sound the way you want at low volumes with extreme settings, but once you crank it the amp isn't gonna like being set that way and will squeal and flub. That said, Mark III's can get pretty nasty and are really tight, so you *could have a problem with the amp, but I'd guess it's your settings. Get the manual, start with the recommended settings and tweak in very small increments from there, you'll be rewarded, they're awesome amps. A tubescreamer type OD will push it over the top if you still need more drive.
And no, you don't have to use Mesa tubes, just don't run any "early breakup" rated tubes in it. They do really like Sylvanias.