I've had a problem with the space vanishing due to "lost" files, but I got it back by uploading some small files (text files etc) to unattached items, then after the sync deleting them, and resyncing again..
It seems that the empeg will reuse the space taken by a "lost" file when the fid numbers catch up..

As to the pause with rebuilding music database, I've had that a few times (I'm also too quick to pull the plug if the sync is taking hours). If you can't get a sync to fix it then you can do the following...
Drop to a shell (with the developer image) and type "rwm" then "exit".
This opens the discs in read write mode, and then "exit" causes the player software to restart. It will rebuild the database and is then able to write it to disc as the static database. I then drop to the shell and exit, which will remount the discs read only. The next boot will be able to read the static database, which stops the pause caused by it rebuilding every time.

Hope that helps someone... =)

(Note, I didn't report the "lost" files as a bug, as I assumed it was caused by me pulling the plug.. Sorry =)

Jazz
(List 112, S/N 00030, 4 gig blue)