Same problem here - actually had it multiple times. I think the device fails to delete the "placeholders" or whatever you call it. The only thing that helped me consistenly is to do a clean resync (rebooting didn't help) - which totally sucks.
Although, you might want to try this (helped me twice but I haven't been able to try the third time)
First try:
1. While your zune device is connected with your zune software, close the zune software.
2. Unplug the device.
3. Plug the device back.
4. Open the Zune software.
Second Try (Same steps but skip steps 2 and 3)
I don't have as much songs as you do and I already get very impatient doing a complete resync - I can only imagine how it would be for you. Yeah, I hope the zune team releases a fix for this, among other things.
Let me know if that worked. :)
Cheers!
Btw, I'm generally happy with my zune. This is just one of the things that get to me.
If you're superficially nice, people will love you just as deep.
