How do you delete music on iTunes Match if already deleted entirely from Mac?
Login to your iTunes Account in iTunes!
On the right hand side, there is a menu where you can click on a button which says: "Bought Content" (i'm a German User). There you have a list of all your media bought on iTunes!

Download your Music which you want to delete again, and then delete it correctly on your Mac!