Could you stitch images where the camera was translated between frames rather than rotated? At least for horizontal paintings, it might be possible to move the camera laterally, keeping the camera and lens parallel to the subject for each shot. Not sure how well the stitching software would handle this.
It might be interesting to test this idea, and some of the other ideas on this topic, by photographing a test pattern consisting of a rectangular grid on a wall. Once you figure out how to correct distortion on this target, use the same technique for a painting. Depending on environment, you might even be able to mount rulers around the painting to guide the correction, then crop them out of the final image.