The searches shouldn't be able to return more results than there are items.
You're saying that the Browse Items page says you have x number of items, but then if you do a search, it says you have more?
Note that you can have more tags than items, because tags can exist even without being applied to any items.
Also, I see another point that could be a source of confusion: you mentioned deleting collections. In Omeka, deleting a collection simply "un-links" all the items that used to be part of that collection. The items, by design, aren't deleted when you delete a collection.