¿Tiene otros dispositivos que utilizan la misma biblioteca?
Yo hice algo similar anoche, eliminado algunas cosas de mi Mac de la biblioteca (archivos de vídeo grandes, alrededor de 800 mb), y luego se fue para iPhone para comprobar el espacio de almacenamiento en iCloud, no se ha cambiado. Y mi 'Recientemente eliminados de los archivos estaba vacío así.
Luego me abrió la aplicación de Fotos en el iPhone, y yo podía notar la 'pop', las miniaturas se movió, así que parece que el iPhone sincronizado que esos videos son eliminados, y después de eso cuando me registré el almacenamiento de iCloud de almacenamiento gratuito fue en aumento.
Así, pruebe a abrir Fotos en otros dispositivos para hacerles sincronización.