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.
