When I delete a song from Zune, I have it set so that it will delete the same song from my phone (sync all music). However, if I delete something from my phone it doesn't get deleted from Zune on my computer when I connect the two through cable (I have wireless sync turned off).
The only saving grace is that even though the song I deleted from my phone still exists on my computer, Zune doesn't try to re-sync it. Still, it's annoying having it in my Zune collection.
I'm running Zune on Windows 7 and the phone is a Lumia 800 running WP 7.8.