It may be helpful to clarify the situation, because re-downloading your movies doesn't actually have anything to do with iCloud - Apple persist in using the name for both and it's confusing a lot of people.
iCloud is your own account which enables syncing of calendar and contacts data, transger of iWork and TextEdit documents between your devices, transfer of photos taken on one device onto all the others, an email service, and the ability to find a lost device which has been set up correctly. It does not provide general file storage, and it does not store your movies or music. It's free at basic level of 5GB for the items mentioned above with extra storage purchasable.
iTunes in the Cloud does not store anything except in the iTunes Store. It simply recognizes that you have previously purchased an item and allows you to re-download it on other devices, or, as you say, re-download it onto the original device if you've deleted it. No extra storage is required because the items are already in the Store. As Julian has pointed out, complicated rights issues means that not all items are available this way, and that different countries have different availablilities. Also if an item is withdrawn from the Store you won't be able to re-download it even if you already purchased it.
iTune Match applies to music (not films) in your collection which you did not purchased from the iTunes Store, but downloaded from elsewhere or ripped from your CDs. If the item exists in the Store it allows you to download a version from there; if not you can upload it to space allocated for you. This facility costs $24.99/£21.99 per year, limit 25,000 songs (purchases do not count towards this limit). This is not part of the iCloud 5GB free storage.
iTunes in the Cloud and iTunes Match require an iTunes account; they do not require an iCloud account.
You're right - it is confusing, and Apple don't help at all with pages like the one below for "iTunes in the Cloud" in which the very first sentence starts "With iCloud..." - yet it's actually an iTunes feature.
They repeatedly mention iCloud as storing the data, even though you don't actually need an iCloud account to use it.
For the avoidance of doubt, are you able to confirm you are looking in the right place for your purchased movies.
You can re-download content purchased from the iTunes store (availability varies depending on location) using the purchased option from the Quick Links section in the top right corner of the iTunes homepage in your iTunes application on your computer.
You can re-download content purchased from the iTunes store (availability varies depending on location) using the purchased option which is revealed in the iTunes app on your iOS device by tapping the more button at the bottom of the screen.
You can re-download content purchased from the iTunes store (availability varies depending on location) using the purchased option which can be found at the top of the screen on the left side when using the movies feature from the Apple TV main menu.
Thanks all for the info. The breakdowns provided byreally helped.
I think I get it now. My movies are connected to my iTunes account, not iCloud.
So.... if I delete the file from my local computer or my iPhone (to save space) I can re-download it at any time on any of my devices that are attached to my Apple ID... provided it's still avail in the iTunes store. Right?
And I totally agree with you Julian: any of the info I found on the Apple website made it seem like this was totally an iCloud thing. No wonder I was confused!!