I think the "hardest" RPG I've ever played was SMT IV, but less because of the actual difficulty of the game and more because the game feels significantly less balanced than Nocturne (Smirking, buffs feel less useful, Demons become irrelevant a lot faster, the removal of random encounters led to a lot of unfair back attacks).

The most challenging game I've ever played (and beaten) would probably be Vagrant Story. I'm still not sure how to beat Guildenstern without Raging Ache and Phantom Pain or spending countless hours looking up a weapon forging FAQ.

(Honorable mention for Zelda 2, tho. That game dragged me through hell and back)