Deleting a file via ADE, or Calibre, is probably different than deleting a sideloaded book - I know for sure that for sideloaded books you *do* need to delete, unplug, replug, then re-add. ADE and Calibre I think are probably updating the database right away?
As far as books not showing up - I actually had a problem for the first time last week, after no problems with ~450 books. I added a couple of books by P.C. Hodgell, and dropped them all in a new directory, "Hodgell, P.C." - turns out the periods in the folder name prevented the KT from finding and processing the new books. Changing the folder to "Hodgell, PC" fixed the problem completely.
Any chance something like this, either in the folder name, file name, title, etc, might be causing the problem? I know I've written software myself that didn't always take weird formatting of filenames and folders into account - the extension is always everything after the *only* period in the filename, right? Who would do something weird like have more than one?