Arigatou gozaimasu derives from the
Japanese adjective, arigatai. This adjective in recent times has meant "thankful", but in older
speech means "hard to find". The transformation from arigatai to arigatou is a sound transformation that occurs with -ai sounds before the polite verb gozaimasu (c.f.
ohayou gozaimasu).
Thus the literal meaning of arigatou gozaimasu is "(such kindness) is hard to find", and not thank you, as most people believe; therefore the two do not exactly correlate. This is part of the reason why people may sometimes use "sumimasen" in place of arigatou gozaimasu, although sumimasen is normally translated as "sorry".
The word arigatai often has Buddhist associations.