because by the "inter" you refer to connections and by the "-net" you imply almost clearly a structured environment.

What does cloud mean, besides something structure-less "out there"?

I'd say because it was first. But then again, it's not unusual to replace established terms after some time to give it some fresh paint.

The "cloud" has always just been a marketing term. If anything I would say it refers to a snapshot of the ongoing IT development at a certain period of time.

The 'internet' is an interconnected network of computers. A cloud is a bit of weather phenomena.

I don't like trying to re-purpose the word cloud, because isn't all that descriptive. Do you have high-availability provided by distributed, load-balanced servers? Maybe. Local mirrors? Maybe. A machine in your basement you rent VM images on to suckers? Maybe.