"Domo arigato gozaimasu/mashita" doesn't literally mean "thank you"--that's the just the English equivalent. "Arigato gozaimasu" is just a polite form of "arigatai," which is an adjective meaning "rare" or "appreciated" or "something that would inspire gratitude." The English is more direct, expressing the speaker's current state of appreciation (remember from grade school that it's really a contraction of "I thank you"). The Japanese version actually praises the act itself: "That is/was/would be a rare thing," which is why sometimes the past tense is appropriate and other times the present (which is also the future) tense fits better.
Writers contributing to the great "Nihonjin-ron" ("Japaneseness theory") industry have done all sorts of nifty analyses of the implications for the historical or national characters of Japanese vs. Englishmen and Americans of these different ways of expressing gratitude. Mostly silly speculation, but kinda fun to read anyway. It makes for good conversation over beer, at any rate.
Karl Friday
Dept. of History
University of Georgia
Athens, GA 30602