I was misinformed about what glHint(GL_PERSPECTIVE_CORRECTION_HINT, GL_NICEST);
was used for in the fixed function pipeline. I was told that this hint should prevent the error that we're seeing above. I've since tested it myself in the fixed function pipeline and it turns out that the hint just controls the perspective correctness of the vertex transformations.
So to fix the problem above, there isn't any solution other than providing projective texture coordinates, which is the solution that most of the other SO questions I've linked to talk about.
I posted the same question to reddit and have recieved a satisfying explenation, source: http://www.reddit.com/r/opengl/comments/1ral2k/perspective_correct_texture_mapping/cdlhw04