I ran some tests here I think you should consider. In general, I have found that I get better quality results when I upscale before interpolating—but it’s much slower. Anyway, it might not help at all since I have not seen similar results to what you describe.
