The problem is the library file in my opinion. I sync via a automated playlist. This playlist holds Music with some Genres, not played in the last X days and has music only for x minutes, ordered by album and track number. If i play a song from the whole library on the PC, the playlist is updated (because of the last played timestamp). If i play a song on the device, the libarary on the device becomes also a new timestamp. This is synced back to the pc and updatest he library and the playlist there to.
This has worked with WMP11 and Windows Mobil 6.x and now with Zune/WP7. But Zune is in some things a little bit crippled :) It would be cool to use WMP again, to sync such things. Its much easier there.