As mentioned, good quality paint will have the biggest effect. If it isn't round, it won't fly straight.
The other thing to watch for on a twist lock barrel, is the fit of the barrel in the body of the mag. If it is loose, the wobble will cause horrible inaccuracies. It happens often with aftermarket barrels. You can fix it by wrapping tape around the barrel just inside the body so that it takes up some of the slack and can't compress the barrel orings as much.
Check the fit of the paint to the barrel or back you are using. The paint should gently touch on two sides opposite each other. That should be consistent with all paint. If it is not sized consistently, then ditch that paint and get some good stuff. If you have bad paint and want the best consistency and forgiveness given that it isn't going to be perfect, use a barrel or back that is oversized. Oversized barrels and backs are much more forgiving on odd sized paint than a tight bore. I use 0.696" for everything. It allows me to shoot any paint without breaking and if an odd sized ball comes along, out the end of the barrel it goes in as straight a line as it can have given the circumstances.
Knock a few fps off the velocity. You would be surprised at the effect on accuracy, especially with bad paint. You won't lose that much distance, because the balls will fly straighter because not as much energy will be lost in the spin.
Except for the Automag in front, its usually the man behind the equipment that counts.