How do I retrieve songs hidden in the iCloud with iTunes 11.0.4?
1) Open iTunes

2) Go to Store

3) Go to Music Tab

4) On the Right Hand Side should be a link "Purchased" - click that.

5) Then "Recent Purchases"

6) Click on the little cloud icon to redownload what you want.

However you should be able to delete from your computer without affecting music on other computers so I am confused by your description of the problem.