[mindonstrike]

What version are you upgrading from?
I had a similiar problem upgrading from 2.014 . It seemed to be related to Hosters main database being reorganized, for instance all my SC spotlights were imported under the generic "Sound Choice" (and that's where they still are) but anything new has to be imported under "Sound Choice Spotlight". So if I go to add a song or reimport a song on "Sound Choice Spotlight" when that disk was imported on "Sound Choice" the database won't show the other songs imported on that disk and it will tell me that number is in use.

As for your deleted numbers: For versions up through 2.014 (I haven't tried it in 2.212 yet) , in order to free up a disk number you not only have to delete the tracks but you MUST delete your Songs.mdb file before you rebuild. Hoster didn't look for tracks you deleted when you rebuilt, it only looked for tracks you added.
This may still be necessary in 2.212 I do not know but it might be worth looking into in case you don't get any better answers.
Good luck.
Sam