When places are deleted, they are not currently being removed from either the hierarchy or the records by status widget. Even without reindexing, they are indeed removed from the index, but the actual locations still show up in the hierarchy viewer. When you click on their entry, you get this message, "Errors occurred when trying to access /index.php/editor/places/PlaceEditor/Edit/place_id/316: * Item has been deleted"
This is a consequence of the new "soft delete" functionality we added. Additional filtering was just added to ensure deleted records don't appear in hierarchies. Can you do an SVN update and let us know how it works for you?