No lo he probado (Match no está disponible para mi país) pero desde el detalles parece que debería ser capaz de eliminar las canciones localmente y confiar en el almacenamiento en la nube para transmitir:
Una vez que tu música está en iCloud, puedes transmitirla a cualquiera de tus dispositivos. Solo tienes que navegar por la lista completa de toda tu música almacenada en la nube. Para escuchar una canción, toca el icono de iCloud junto a ella y la canción empezará a sonar. Puedes almacenar hasta 25.000 canciones en iCloud (más si las canciones se compran en el iTunes Store), pero solo se almacena en tu dispositivo lo que quieres reproducir. Así tienes acceso inmediato a una enorme biblioteca musical sin ocupar espacio de almacenamiento.
Echa un vistazo a esto Discusión sobre Mac Rumors Parece que después de emparejar una canción e intentar borrarla, se guarda una copia en el disco duro para poder reproducirla más rápido y no volver a descargarla.
Edición: Supongo que eres consciente de los peligros de confiar únicamente en el almacenamiento en la nube para tu biblioteca musical: sólo funcionará mientras esté conectado a la nube, la disponibilidad está sujeta a la benevolencia de Apple (con poca garantía) y las condiciones de uso podrían cambiar en cualquier momento.