Help with recreating deleted categories

Something odd is happening. I had some categories that were deleted. They no longer show up in the manage/category list, but do show up in the list of check boxes for categorizing a post. I want these categories back, but if I try to recreate them, it says they already exist.

Why are they not showing on the manage page, but are available for posts, and how can I get them back?

Is there a way to delete them from the database and recreate them? Any help is really appreciated.