I know that a lot of people are complaining about this but I believe I have some info that could help.
I posted a question like this when I first got my zune hd and saw the problem. Sadly, no one helped me so I tried to figure it out myself. I tested it with my older zune 30 brick and it didn't have any issues. After being frustrated I gave up. Later on I noticed that the "recently played" songs that were actually syncing were the songs I was playing when the zune hd was NOT in locked mode. So, basically, it turns out that every song played when the zune is in locked mode does not get uploaded to the play count when synced. This is a problem since I ALWAYS lock my zune but even if I wanted to try to leave it unlocked I couldn't because it automatically locks after a brief period of time.
Try it zune hd owners. The problem is the lock feature.