I found 4k emails in Limbo - created a segment that caught them all. Created the segment into a group. Archived the group, then deleted. Our contact list should only be about 4,500, but still shows 8k.
If you deleted the segment itself, that doesn't do anything to the contacts that were in that segment.
You'll first want to actually delete the contacts, then you could delete the segment if you no longer wanted it.
You'll Archive the contacts using that ACTIONS button I pointed out in my reply to your other post:
So I would recommend recreating that LIMBO segment, then open it up and click ACTIONS and ARCHIVE ALL .
Once you do this, it may take a bit for the Home screen to reflect the changes, but to make sure you've done it right, click CONTACTS from the AUDIENCE page. The number beside the word ACTIVE will be a more specific and accurate count.