iCloud still full after deleting lots of messages
Wait for some time and check again. It may take a little while for the messages to be purged on the iCloud servers and for the updated storage space to be reported on the device.