Nothing gets deleted from 3D Warehouse (that doesn’t violate any terms or rights). Probably there are just that many more 3D objects now or the search isn’t that good. The search is not a good proof for existence, but links are, e.g.:
Try the advanced search tools and add criterions that exclude the bulk of models. If you know a specific model that you believe is missing now, can you describe what it is?