I moved this part to the top b/c it is my ultimate suggestion:
Last thing: having this specific image as the source, I'd not even bother to waste more than 3 minutes on transforming. Rather, I'd do it manually. You can select one row at a time and manually move it in 0 or 1 pixels to the right, relative to the row below.
How far are you stretching it? If it is to more than a few dozens %, then you can't resize without noticeable blur. There is not enough information in the original to construct a much higher resolution transformation and blending of adjacent pixel values must be performed to generate the interpolated pixel - which is the source for the blur.
Also, when using such a high zoom ratio you are more likely to see the blurring of the stretched image than when viewing at 1:1.
EDIT after seeing the images: It looks like the "fuzziness" you see is the inevitable result of the skewing. I am not familiar with PS as I mentioned earlier, but I can imagine that you have a anti-aliasing switch in the transform dialog. Try to turn it off and see what happens. Otherwise, you may be able to control the interpolation (sampling) algorithm (bilinear, biqubic, lanczos, etc.) If you can disable interpolation, it should remove this fuzziness.