I don't think the playlists are the source of the trouble. I believe that MC creates the playlists on the device to reflect what was synced, and so that you can use those playlists on your device as well. Their incorrect contents are symptoms, but not the cause.
MC creates a database file on the device (Database.mpl) and this list is used to hint at what files MC has synced to the device. I believe MC compares the sync playlists or files against this list, but it also does some more internal magic.
Over the past year, many bugs in this area have been squashed. At least one still remains - that is, when metadata changes for a file, sometimes the sync process fails to match up the new file and its metadata with the old one, and you'll get duplicates. This typically happens when you change something like the album name, or artist.
Another bug I suppose is that the status indicated in the sync status queue is not very reliable for what MC will actually do. Sometimes it tells you that some files will be deleted, sometimes it doesn't and just does the work anyway. (In my opinion, this area needs a major overhaul, as over the years, I and others have found HH sync to be troublesome and fairly unreliable).
Ultimately, I've created a process that works well most of the time, and occasionally I have to delete a duplicate file or two. The process I use makes this pretty easy now (for me anyway).
A key step is to first ensure that you are starting with a clean slate, removing everything from the virtual HH directory, including the Database.mpl, and have MC perform a full sync.
Each time I sync, I open both the virtual HH view, and my Sync List smartlist, and take note of how many files are indicated on each. They should always been the same at the end of the sync, and when they are not, this indicates MC has failed to correctly match a file with changed metadata with an existing file on the HH. And then I have to find which file(s) are duplicated. Often the log messages indicate which files were problematic (I keep logging always enabled), and other times I have to export both views so that I can sort and compare them. This always yields the differences, and then I manually delete the HH files that MC didn't delete.
My views (Sync List and Fake HH) contain a single column - the MC "MatchKeyExpression" value. This is a calculated value that MC uses to determine whether or not two files are the same. For Audio files, it is tantamount to:
[Name] Clean([Artist], 1) [Album] [Genre] FormatNumber([Track #,0]) [Media Type]
By exporting these views as CSV files, I can sort and diff the files easily, to find the problems.
So, start with a clean slate, enable logging, and then do your sync and check the results by checking the file counts.