Interesting Sentence Construct. Arigatou Origin?

While meeting with my Sensei yesterday, we were discussing how to say "Thank you for x". The teacher explained that the following sentence structure could be used:

N wo arigatou

This type of structure is a very common one in Japanese, where the N(oun) is a direct object of the last word which is a verb. At that point I had to ask "is arigatou a verb?". This led to some interesting conversation of which I can't say I have a complete understanding, but the basic idea is as follows. There used to be a grammar construct which is very rarely used now, but was much more commonly used in the distant past. It is as follows:

V-stem + gatai

Which meant "difficult to do V(erb)." For instance, difficult to eat would be tabegatai, or difficult to sleep would be negatai. Apparently arigatou used to be arigatai. I'm not sure how "difficult to have" (or any other of the several variations in meaning of arimasu) eventually became "thank you" but it kind of made sense when Sensei explained it :) As a side note, the V-stem + gatai grammar construct has been replaced with V-stem + nikui for meaning "difficult to V".