I do have a back up. I deleted the songs from within iTunes. I selected the entire library and deleted them (I did not check delete from iCloud). It is werid that I can play any song on my iphone from icloud but not from the imac.
There is no cloud beside the songs themselves but the status shows matched, uploaded or purchased. Note the purchased songs (which play perfectly) don't nescessarliy have a cloud beside them either. (some do)
From your description you deleted the files from the OS X File system (i.e. the iTunes folder) and not from within the iTunes application. This is why the tracks have an exclamation point and can not be played. To be able to stream the tracks while in iTunes highlight all the tracks in the library and delete them but do not remove them from the cloud.
In the future, all track management, including deleting, needs to take place in the iTunes application.