as a native speaker of German, my feeling is that the difference is purely stylistic. It has a lot to do with the language of advertising. If anyone ever cared to research the history of the usage of the three, I'm sure they would find that "kostenlos" is a bit oldfashioned - it is definitely the most German of the three and hence not so popular anymore (today, everything that is fashionable has to be English
) "Gratis" is of Latin origin and my dictionary tells me it entered the German language in the 16th century - hence it has a high standard stylistically. "Umsonst" has the connotation "worthless" because of its other meaning that you pointed out yourself, so it suggests that something is free but not very good. As a matter of fact, many shops use the English word "free" now, and under the influence of advertising, teenagers (at least the ones I know
are in process of forgetting that "gratis" exists.
I hope that helped!