IPhone – iCloud still full after deleting lots of messages

Your answer lies deep in the settings app on your iPhone.

Go to iCloud - Storage & Backup - Manage Storage - your device

Backup settings allow you to save space in iCloud by excluding app data in the next back up. You can toggle on more and more buckets of data until the estimate is low enough to allow the next backup attempt to succeed.

When you turn off data under iOS 7 where it says Backup Options: Choose the data you want to back up. - this does delete the backup copy of that data, so consider paying for more space (or cleaning up elsewhere) if you cannot afford to lose that backup copy.

Assuming you have data you are willing to risk losing or is backed up to iTunes on a computer, then you can clean enough space and add things back slowly (triggering another backup after each addition) once a small minimal backup has been completed successfully.

Furthermore, if you go to the above screen and turn off Camera Roll backup, it will prompt you to delete these files from the iCloud server backup, freeing the space immediately (just because you delete the videos on the device, they take up backup space on iCloud until you purge the backup by category or delete it entirely and start over).

Your iCloud space has to remain full of files that were backed up and now deleted on the device for it to function. After a few days of backups, the old backups expire and no longer take space but in your case you might want to purge them intentionally rather than wait for it to happen programatically.

You may find your answer here.

To summarize there is no empty trash like there was in iPhoto. Deleted pictures are moved to a recently deleted album and then automatically deleted permanently after 30 days. They can be manually removed or recovered at any time during these 30 days.