The words “you are welcomed” are of course not always to be marked as incorrect—there are contexts where they are grammatical, idiomatic, and the exact right phrase to use. For example,
When you step off the ship, you are welcomed by girls in bast skirts who throw flower wreaths around your neck.
This example shows that you are welcomed is a passive construction: the agent (that is, the logical subject) are the exotic girls, and the patient (that is, the logical object) is ‘you’. So really, it means,
When you step off the ship, girls in bast skirts who throw flower wreaths around your neck welcome you.
In other words, welcomed is the past participle of the verb to welcome.
This verb, in itself, is derived by zero-derivation—which is an extremely common and productive way of forming new words in English, probably the most common of all types of derivation—from the word welcome.
Welcome itself started out as an adverb modifying a past participle; that is, it started out being the verb come with the adverb well, at least on some notional level. The only form of that construction that probably ever really had any currency, though, was the past participle—but that construction had so much currency that it was soon univerbated. This was very long ago, though, before there was any such thing as ‘English’.
Throughout the course of English, this original participle (i.e., adjectival unit) became used as an interjection, spawned a noun form with which it later coalesced entirely, and ultimately also spawned the verb to welcome. Note that derived verbs always end up being regular, even if they’re derived from something derived from an irregular verb. See the last paragraphs and the comments to this answer for a bit more on this. The upshot is that the past tense and past participle of welcome are both welcomed (regular), not *welcame and *welcome.
So unlike many other English adjectives, the adjective welcome does not double as a participle, but is exclusively a pure adjective. “*I have welcome him” is quite ungrammatical.
I’m going to disagree with part of what you state in your question here and say that welcomed is the opposite: it is purely a part of the verbal paradigm of to welcome; that is, it is only a participle, not an adjective. The two examples you give (“a welcomed change” and “would be very welcomed”) are both ungrammatical to me. Welcome is the word to use here. This is probably not universally true (I’m sure there are examples of both even in printed books), but it is at least true that in ‘Standard English’, welcome is infinitely more common as an adjective than welcomed.
Accepting that, it should be reasonably clear why “You’re welcomed!” doesn’t work as the answer to a thank-you: it is a passive construction meaning that someone is welcoming you, rather than a simple description of the subject with an adjective (in this case welcome).
So in that particular usage, I would say “You’re/You are welcome” is indeed always the right option, and “You are welcomed” is always wrong.
As for why it’s not “You’re welcoming”, rather than “You’re welcome”, that is simple semantics. One of the meanings of welcome is that which you quote: not obligated, free from the pressure of having social obligations towards someone (in a given context). Welcoming just does not have this meaning at all. Unlike welcome(d), welcoming is a participle that doubles as an adjective, and its meaning is same as most other present participles doubling as adjectives: the meaning of the base verb, expressed as an adjectival attribute of whatever the adjective is modifying.
Unlike Josh’s now deleted answer, I would not call “You’re welcome” an idiom. An idiom is essentially something that is ‘more than the sum of its parts’: even if you know the appropriate, relevant meanings of all the words involved, you still cannot figure out what the phrase means. You just have to know. As a generic platitude, there is a certain level of idiomacy to the very utterance itself, regardless of what you say. “You’re welcome”, “no worries”, “it was nothing”, “don’t mention it”, etc., all have a direct surface meaning that is easy to understand and can be correctly deduced from the meanings of the individual words.
The idiomatic bit is that they are used in this particular fashion, as a formulaic response to a thank-you. But unless you have a specific word whose main denotation is specifically a formulaic response to a thank-you or you use a completely transparent construction like “You do not have to say thank you”, that is pretty much bound to be true of any variant used, and I personally don’t think that’s enough to call the phrase itself an idiom.
