Jonathan,
Did you try straightening them in Photoshop before stitching them? I have used Canon's PhotoStitch, but it always leaves a sort of fuzzy boundary. I'm sure there are better programs, but if you can correct the rotation without resizing the photos, it should work.
Dale

