Well, it does store information about the deleted tracks on the computer -- else how would it know which tracks to delete when you hit sync?

Maybe I'll have time to take a quick look at it today. In the meantime, two suggestions:

1. Try jemplode
2. Try creating some more playlists, and moving the tracks in batches from the huge playlist into those playlists. Sync, and then delete+sync those playlists one at a time. Don't forget that there might still be some bugs in beta11 when you do multiple syncs in a single session.