I've been doing extensive testing with conversion / syncing to handhelds, and discovered a number of issues. Most of them have now been resolved in MC, but this one (if its the same) is the remaining one.
Is it correct to assume you have enabled the setting: "Delete in handheld any files not in sync list"?
If so, I wonder if you might enable logging, and try a sync. When a file fails to be deleted, it might be interesting if you search the log to see if you have any lines containing:
CreateDeleteArray: Not deleting
and take note if those are the not-deleted tracks.