This や is an old 終助詞 which is described here. It's probably similar to the English exclamation mark, or "Oh/O" seen in verses and lyrics. Basically it is only found in old Japanese and haiku. (や used in Kansai-ben is different from this, I think)
In modern Japanese usage, ありがたや sounds archaic as compared to ありがたい. It sounds as if you were jokingly simulating a person in the past who is faithfully worshiping Japanese 神 and 仏. Or it sounds like you were thanking for something in an exaggerated manner, as if you saw a miracle of God.
A typical usage of ありがたや can be found in this page introducing a VPN router. The men in the picture are worshiping the almighty router!
Don't use it in formal situations, because ありがたや is usually used jokingly like this.
I think かたじけない is already an archaic, samurai-like wording, and people use it only as a joke today. So I see very little difference between かたじけなや and かたじけない. Theoretically though, the former is more emphatic.